HackerRank Range query:

You are given an array A of n integers. You have to perform m queries on the array. The queries are of two types:

  1. Modify the ith element of the array.

  2. Given x, y, print min{Ai + Ai+1 +…+ Aj | x ≤ i ≤ j ≤ y}.

Note: A brute force solution may not work; Try using an efficient data structure. Use fast I/O to avoid TLE.

Input Format

The first line contains an integer t denoting the number of test cases.

The next line consists of an integer n.

The following line contains n integers representing the array A.

The next line contains an integer m denoting the number of queries.

The following m lines contain integers of the form given below.

  • 0 x y: modify Ax into y
  • 1 x y: print min{Ai + Ai+1 +…+ Aj | x ≤ i ≤ j ≤ y}


1 ≤ t ≤ 100

1 ≤ n ≤ 50000

-10000 ≤ Ai ≤ 10000

0 ≤ m ≤ 50000

Output Format

For each query print the output as specified.

My Solution


  1. Calculate prefix sums prefix_sums for the given array.
  2. For the given interval, move from left to right and keep track of the largest encountered value max_prefix_sum of prefix_sums and the minimum subsum min_subsum (min_subsum = min(prefix_sums[i] - max_prefix_sum) for left=<i<=right). In the end, min_subsum is the answer.
  3. If some value of the initial array is updated then prefix_sums must be updated accordingly.

The overall time complexity of the algorithm is O(n2). The space complexity is O(n). I know that for a O(n2) time complexity solution I don't need any additional array and there's a more elegant solution for this based on Maximum Subarray Problem. However, it feels like with prefix sums I have a better chance of having a O(nlogn) or O(n1.5) time complexity solution.


import itertools

class MinSumRangeQuery:
    prefix_sums = None

    def __init__(self, array):
        self.prefix_sums = list(itertools.accumulate(array))

    def update(self, index, value):
        diff = value - array[index]
        for i in range(index, len(self.prefix_sums)):
            self.prefix_sums[i] += diff

    def min_subarray_sum(self, left, right):
        if left == right:
            return self.prefix_sums[left]

        min_subsum = 99999999
        max_prefix_sum = self.prefix_sums[left - 1]
        for i in range(left, right + 1):
            current_subsum = self.prefix_sums[i] - max_prefix_sum

            if min_subsum > current_subsum:
                min_subsum = current_subsum

            if max_prefix_sum <= self.prefix_sums[i]:
                max_prefix_sum = self.prefix_sums[i]

        return min_subsum

for _ in range(int(input())):
    n = int(input())
    array = [int(i) for i in input().split()]
    array.insert(0, 0)
    minSumRangeQuery = MinSumRangeQuery(array)

    for _ in range(int(input())):
        a, x, y = [int(i) for i in input().split()]
        if a == 1:
            print(minSumRangeQuery.min_subarray_sum(x, y))
        elif a == 0:
            if array[x] != y:
                minSumRangeQuery.update(x, y)


Given the constraints above, the code times out for all but a default test case. What's a more efficient way to solve the problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.