Given an integer array A and a range, find a subarray within the range with a minimum sum

Question

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(n²). The space complexity is O(n). I know that for a O(n²) 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(n^1.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?

Answer 1

Introduction

I have come up with a more efficient solution in terms of the time complexity, although it's still not passing all the test cases. Nevertheless, I decided to post the solution, because it may help someone with a similar problem in the future.

Explanation

The idea is to divide an initial array into segments of size √n, and for each segment to pre-calculate 4 helper arrays - sum of elements, minimum sum of elements, minimum prefix sum (minimum sum starting from the first element of the bucket) and minimum suffix sum (minimum sum ending at the last element of the bucket).

In such case, there are 3 possible use cases when calculating the min sum:

1. Sum range is within the same bucket. Then, to calculate the minimum subsum there, do it brute force.

2. Sum range starts in one bucket and ends in a neighbouring bucket. Again, do brute force.

3. Sum range covers more than 2 buckets. That's the hardest case, and that's what for all the additional arrays are built. The minimum sum in the range can happen to be a minimum subsum in some bucket, or a minimum prefix, or a suffix, or a sum of the min suffix and prefix (both buckets are in the range), or a sum of all elements in the current bucket and "special" sum from previous matching buckets. The "special" sum is either a min suffix from the preceding matching bucket or sum of elements starting from some min suffix. Please see the code for more details.

When a value is updated, all 4 helper arrays have to be updated too, and that is done in O(√n) time.

Code

import math
import sys

class MinSumRangeQuery:
    size = None
    array = None

    bucket_size = None
    bucket_sums = None
    min_prefix_sums = None
    min_suffix_sums = None
    min_subarray_sums = None

    def __init__(self, array):
        self.size = len(array)
        self.array = array

        self.bucket_size = int(math.sqrt(self.size))
        self.bucket_sums = [None] * (self.bucket_size)
        self.min_prefix_sums = [None] * (self.bucket_size)
        self.min_suffix_sums = [None] * (self.bucket_size)
        self.min_subarray_sums = [None] * (self.bucket_size)

        left = 0
        for i in range(self.bucket_size):
            right = left + self.bucket_size

            # sum of elements in a bucket
            self.bucket_sums[i] = sum(self.array[left:right])
            # calculate a min sum starting from the left position
            self.min_prefix_sums[i] = self.find_min_prefix(left, right)
            # calculate a min sum ending at the right position
            self.min_suffix_sums[i] = self.find_min_suffix(left, right)
            # calculate a min sum within the bucket
            self.min_subarray_sums[i] = self.find_min_subsum(left, right)
            left += self.bucket_size

    def find_min_prefix(self, left, right):
        min_prefix = self.array[left]
        current_prefix = min_prefix
        for i in range(left + 1, right):
            current_prefix += self.array[i]
            if current_prefix < min_prefix:
                min_prefix = current_prefix

        return min_prefix

    def find_min_suffix(self, left, right):
        min_suffix = self.array[right - 1]
        current_suffix = min_suffix
        for i in range(right - 2, left - 1, -1):
            current_suffix += self.array[i]
            if current_suffix < min_suffix:
                min_suffix = current_suffix

        return min_suffix

    def find_min_subsum(self, left, right):
        current_min_subsum = 0
        min_subsum = sys.maxsize

        for i in range(left, right):
            current_min_subsum = min(current_min_subsum + self.array[i],
                                     self.array[i])
            if current_min_subsum < min_subsum:
                min_subsum = current_min_subsum

        return min_subsum

    def find_min_in_range(self, left, right):
        current_bucket_id = int(left / self.bucket_size)
        end_bucket_id = int(right / self.bucket_size)
        current_right = min((current_bucket_id + 1) * self.bucket_size, right)

        current_min_subsum = self.find_min_suffix(left, current_right)
        min_sum = self.find_min_subsum(left, current_right)

        current_bucket_id += 1
        while current_bucket_id < end_bucket_id:
            min_prefix = self.min_prefix_sums[current_bucket_id]
            min_subsum = self.min_subarray_sums[current_bucket_id]
            min_suffix = self.min_suffix_sums[current_bucket_id]

            min_sum = min(min_sum, min_prefix + current_min_subsum)
            min_sum = min(min_subsum, min_sum)

            current_min_subsum = min(current_min_subsum + self.bucket_sums[current_bucket_id],
                                     min_suffix)
            min_sum = min(current_min_subsum, min_sum)

            current_bucket_id += 1

        current_left = current_bucket_id * self.bucket_size
        #if current_left < right:
        min_prefix = self.find_min_prefix(current_left, right)
        min_sum = min(current_min_subsum + min_prefix, min_sum)
        min_sum = min(self.find_min_subsum(current_left, right), min_sum)

        return min_sum

    def update(self, index, value):
        bucket_index = int(index / self.bucket_size)
        if bucket_index < self.bucket_size:
            self.bucket_sums[bucket_index] += (value - self.array[index])
        self.array[index] = value
        if bucket_index < self.bucket_size:
            left = bucket_index * self.bucket_size
            right = left + self.bucket_size
            self.min_suffix_sums[bucket_index] = self.find_min_suffix(left, right)
            self.min_prefix_sums[bucket_index] = self.find_min_prefix(left, right)
            self.min_subarray_sums[bucket_index] = self.find_min_subsum(left, right)

tests = int(input())

for i in range(tests):
    size = int(input())

    array = [int(i) for i in input().split()]

    minSumRangeQuery = MinSumRangeQuery(array)

    queries = int(input())

    for _ in range(queries):
        a, x, y = [int(i) for i in input().split()]
        x -= 1

        if a == 1:
            print(minSumRangeQuery.find_min_in_range(x, y))
        elif a == 0 and array[x] != y:
            minSumRangeQuery.update(x, y) 

Algorithm Complexity

Time complexity of the algorithm is O(n√n), and space complexity is O(√n) because 4 arrays for each bucket have to be maintained.