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.