GenomicRangeQuery

Find the minimal nucleotide from a range of sequence DNA
ℹ️ © Codility, 2009-2018

Problem

A DNA sequence can be represented as a string consisting of the letters ‘A’, ‘C’, ‘G’ and ‘T’, which correspond to the types of successive nucleotides in the sequence. Each nucleotide has an “impact factor”, which is an integer. Nucleotides of types ‘A’, ‘C’, ‘G’ and ‘T’ have impact factors of 1, 2, 3 and 4, respectively. You are going to answer several queries of the form: “What is the minimal impact factor of nucleotides contained in a particular part of the given DNA sequence?”.

The DNA sequence is given as a non-empty string S = “S[0] S[1] … S[n – 1]” consisting of n characters. There are m queries, which are given in non-empty arrays P and Q, each consisting of m integers. The k^th query (0 ≤ k < m) requires you to find the minimal impact factor of nucleotides contained in the DNA sequence between positions P[k] and Q[k] (inclusive).

For example, consider string S = “CAGCCTA” and arrays P, Q such that: P[0] = 2, Q[0] = 4, P[1] = 5, Q[1] = 5, P[2] = 0, Q[2] = 6.
The answers to these m = 3 queries are as follows:
• The part of the DNA between positions 2 and 4 contains nucleotides ‘G’ and ‘C’ (twice), whose impact factors are 3 and 2 respectively, so the answer is 2;
• The part between positions 5 and 5 contains a single nucleotide ‘T’, whose impact factor is 4, so the answer is 4;
• The part between positions 0 and 6 (the whole string) contains all nucleotides, in particular nucleotide ‘A’ whose impact factor is 1, so the answer is 1.

Write a function that, given a non-empty string s consisting of n characters and two non-empty arrays P and Q consisting of m integers, returns an array consisting of m integers specifying the consecutive answers to all queries.

Result array should be returned as an array of integers.

For example, given the string S = “CAGCCTA” and arrays P, Q such that: P[0] = 2, Q[0] = 4, P[1] = 5, Q[1] = 5, P[2] = 0, Q[2] = 6, the function should return the values [2, 4, 1], as explained above.

Assume that:
• n is an integer within the range [1 … 100,000];
• m is an integer within the range [1 … 50,000];
• each element of arrays P, Q is an integer within the range [0 … n – 1];
• P[k] ≤ Q[k], where 0 ≤ k < m;
• string S consists only of upper-case English letters ‘A’, ‘C’, ‘G’, ‘T’.

Complexity:
• expected worst-case time complexity is O(n + m);
• expected worst-case space complexity is O(n) (not counting the storage required for input arguments).

Solution

C#

class Solution {
  public int[] solution(string S, int[] P, int[] Q) {
    int n = S.Length;
    int[] A = new int[n + 1];
    int[] C = new int[n + 1];
    int[] G = new int[n + 1];
    A[0] = 0;
    C[0] = 0;
    G[0] = 0;
    for (int i = 0; i < n; i++) {
      A[i + 1] = A[i] + (S[i] == 'A' ? 1 : 0);
      C[i + 1] = C[i] + (S[i] == 'C' ? 1 : 0);
      G[i + 1] = G[i] + (S[i] == 'G' ? 1 : 0);
    }
    int m = P.Length;
    int[] R = new int[m];
    for (int k = 0; k < m; k++) {
      if (A[Q[k] + 1] - A[P[k]] > 0) {
        R[k] = 1;
      } else if (C[Q[k] + 1] - C[P[k]] > 0) {
        R[k] = 2;
      } else if (G[Q[k] + 1] - G[P[k]] > 0) {
        R[k] = 3;
      } else {
        R[k] = 4;
      }
    }
    return R;
  }
}

Java

class Solution {
  public int[] solution(string S, int[] P, int[] Q) {
    int n = S.length();
    int[] A = new int[n + 1];
    int[] C = new int[n + 1];
    int[] G = new int[n + 1];
    A[0] = 0;
    C[0] = 0;
    G[0] = 0;
    for (int i = 0; i < n; i++) {
      A[i + 1] = A[i] + (S.charAt(i) == 'A' ? 1 : 0);
      C[i + 1] = C[i] + (S.charAt(i) == 'C' ? 1 : 0);
      G[i + 1] = G[i] + (S.charAt(i) == 'G' ? 1 : 0);
    }
    int m = P.length;
    int[] R = new int[m];
    for (int k = 0; k < m; k++) {
      if (A[Q[k] + 1] - A[P[k]] > 0) {
        R[k] = 1;
      } else if (C[Q[k] + 1] - C[P[k]] > 0) {
        R[k] = 2;
      } else if (G[Q[k] + 1] - G[P[k]] > 0) {
        R[k] = 3;
      } else {
        R[k] = 4;
      }
    }
    return R;
  }
}

JavaScript

function solution(S, P, Q) {
  var n = S.length;
  let A = [];
  let C = [];
  let G = [];
  A[0] = 0;
  C[0] = 0;
  G[0] = 0;
  for (let i = 0; i < n; i++) {
    A[i + 1] = A[i] + (S[i] == 'A' ? 1 : 0);
    C[i + 1] = C[i] + (S[i] == 'C' ? 1 : 0);
    G[i + 1] = G[i] + (S[i] == 'G' ? 1 : 0);
  }
  let m = P.length;
  let R = [];
  for (let k = 0; k < m; k++) {
    if (A[Q[k] + 1] - A[P[k]] > 0) {
      R[k] = 1;
    } else if (C[Q[k] + 1] - C[P[k]] > 0) {
      R[k] = 2;
    } else if (G[Q[k] + 1] - G[P[k]] > 0) {
      R[k] = 3;
    } else {
      R[k] = 4;
    }
  }
  return R;
}

PHP

function solution($S, $P, $Q) {
  $n = strlen($S);
  $A = [];
  $C = [];
  $G = [];
  $A[0] = 0;
  $C[0] = 0;
  $G[0] = 0;
  for ($i = 0; $i < $n; $i++) {
    $A[$i + 1] = $A[$i] + ($S[$i] == 'A' ? 1 : 0);
    $C[$i + 1] = $C[$i] + ($S[$i] == 'C' ? 1 : 0);
    $G[$i + 1] = $G[$i] + ($S[$i] == 'G' ? 1 : 0);
  }
  $m = count($P);
  $R = [];
  for ($k = 0; $k < $m; $k++) {
    if ($A[$Q[$k] + 1] - $A[$P[$k]] > 0) {
      $R[$k] = 1;
    } else if ($C[$Q[$k] + 1] - $C[$P[$k]] > 0) {
      $R[$k] = 2;
    } else if ($G[$Q[$k] + 1] - $G[$P[$k]] > 0) {
      $R[$k] = 3;
    } else {
      $R[$k] = 4;
    }
  }
  return $R;
}