Kth Smallest Subarray Sum - Leetcode Solution

Problem Statement:

Given an integer array nums of length n and an integer k, return the kth smallest subarray sum.

A subarray is defined as a non-empty contiguous sequence of elements in an array. A subarray sum is the sum of all elements in the subarray.

Example 1:

Input: nums = [1,2,3], k = 4 Output: 7 Explanation: The subarrays of nums are [1], [2], [3], [1,2], [2,3], and [1,2,3]. The sorted subarrays in non-decreasing order are [1], [1,2], [1,2,3], [2], [2,3], and [3]. The 4th smallest subarray is [1,2,3]. Example 2:

Input: nums = [1], k = 1 Output: 1

Approach:

The brute force approach is to first generate all the subarrays and then sort them and find the kth smallest subarray sum. The time complexity of this approach will be O(n^3logn).

In order to solve this problem efficiently, we can use binary search. We can fix a lower and upper limit and check if the mid is the kth smallest subarray sum. We can check this by counting the number of subarrays whose sum is less than or equal to the mid. If the count is equal to k, then mid is the kth smallest subarray sum. Otherwise, if the count is less than k, then we need to search in the upper half and if the count is greater than k, then we need to search in the lower half.

Algorithm:

1. Create a function countSubarray that takes an array nums of length n and an integer mid and returns the number of subarrays whose sum is less than or equal to mid.
2. Initialize count to 0.
3. Initialize left to 0 and right to 0. Traverse the array nums and for each element add it to the current sum. If the current sum is less than or equal to mid, increment count. Otherwise, increment left until the sum becomes less than or equal to mid. Then decrement count.
4. Increment right and repeat step 3 until right is equal to n.
5. Return count.
6. Initialize left to the minimum element of the array and right to the sum of all elements of the array.
7. While left is less than right, do the following: a. Initialize mid to (left+right)/2. b. If countSubarray(nums, mid) is less than k, set left to mid+1. c. Otherwise, set right to mid.
8. Return left.

Time Complexity:

The time complexity of countSubarray function is O(n) as we are traversing the array only once. The time complexity of the binary search algorithm is O(log(sum(nums)-min(nums))), where sum(nums) denotes the sum of all elements of nums and min(nums) is the minimum element of nums.

Therefore, the overall time complexity of the algorithm is O(nlog(sum(nums)-min(nums))).

Space Complexity:

The space complexity of the algorithm is O(1) as we are not using any extra data structures.

Python Code:

class Solution: def countSubarray(self, nums: List[int], mid: int) -> int: count = 0 left = 0 sumVal = 0 for right in range(len(nums)): sumVal += nums[right] while left <= right and sumVal > mid: sumVal -= nums[left] left += 1 count += right - left + 1 return count

def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:
    left = min(nums)
    right = sum(nums)
    while left < right:
        mid = (left + right) // 2
        if self.countSubarray(nums, mid) < k:
            left = mid + 1
        else:
            right = mid
    return left

Java Code:

class Solution { public int countSubarray(int[] nums, int mid) { int count = 0; int left = 0; int sumVal = 0; for (int right = 0; right < nums.length; right++) { sumVal += nums[right]; while (left <= right && sumVal > mid) { sumVal -= nums[left]; left++; } count += right - left + 1; } return count; }

public int kthSmallestSubarraySum(int[] nums, int k) {
    int left = Integer.MAX_VALUE;
    int right = 0;
    for (int num : nums) {
        left = Math.min(left, num);
        right += num;
    }
    while (left < right) {
        int mid = (left + right) / 2;
        if (countSubarray(nums, mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

}

1