2
\$\begingroup\$

Problem

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}

Constraints

1 ≤ t ≤ 100

1 ≤ n ≤ 50000

-10000 ≤ Ai ≤ 10000

0 ≤ m ≤ 50000

Output Format

For each query print the output as specified.

My Solution

Algorithm

  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.

Code

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)

Question

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?

\$\endgroup\$

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.