Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/1918.html

1918. Kth Smallest Subarray Sum

Level

Medium

Description

Given an integer array nums of length n and an integer k, return the k-th 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 = [2,1,3], k = 4

Output: 3

Explanation: The subarrays of [2,1,3] are:

  • [2] with sum 2
  • [1] with sum 1
  • [3] with sum 3
  • [2,1] with sum 3
  • [1,3] with sum 4
  • [2,1,3] with sum 6

Ordering the sums from smallest to largest gives 1, 2, 3, 3, 4, 6. The 4th smallest is 3.

Example 2:

Input: nums = [3,3,5,5], k = 7

Output: 10

Explanation: The subarrays of [3,3,5,5] are:

  • [3] with sum 3
  • [3] with sum 3
  • [5] with sum 5
  • [5] with sum 5
  • [3,3] with sum 6
  • [3,5] with sum 8
  • [5,5] with sum 10
  • [3,3,5], with sum 11
  • [3,5,5] with sum 13
  • [3,3,5,5] with sum 16

Ordering the sums from smallest to largest gives 3, 3, 5, 5, 6, 8, 10, 11, 13, 16. The 7th smallest is 10.

Constraints:

  • n == nums.length
  • 1 <= n <= 2 * 10^4
  • 1 <= nums[i] <= 5 * 10^4
  • 1 <= k <= n * (n + 1) / 2

Solution

Use binary search. The maximum subarray sum is the sum of all elements in nums and the minimum subarray sum is the minimum element in nums. Initialize high and low as the maximum subarray sum and the minimum subarray sum. Each time let mid be the mean of high and low and count the number of subarrays that have sum less than or equal to mid, and adjust high and low accordingly. Finally the k-th smallest subarray sum can be obtained.

To count the number of subarrays that have sum less than or equal to mid, use sliding window over nums and for each index, count the number of subarrays that end at the index with sum less than or equal to mid.

  • class Solution {
    public int kthSmallestSubarraySum(int[] nums, int k) {
        int min = Integer.MAX_VALUE, sum = 0;
        for (int num : nums) {
            min = Math.min(min, num);
            sum += num;
        }
        int low = min, high = sum;
        while (low < high) {
            int mid = (high - low) / 2 + low;
            int count = countSubarrays(nums, mid);
            if (count < k)
                low = mid + 1;
            else
                high = mid;
        }
        return low;
    }

    public int countSubarrays(int[] nums, int threshold) {
        int count = 0;
        int sum = 0;
        int length = nums.length;
        int left = 0, right = 0;
        while (right < length) {
            sum += nums[right];
            while (sum > threshold) {
                sum -= nums[left];
                left++;
            }
            count += right - left + 1;
            right++;
        }
        return count;
    }
}

############

class Solution {
    public int kthSmallestSubarraySum(int[] nums, int k) {
        int l = 1 << 30, r = 0;
        for (int x : nums) {
            l = Math.min(l, x);
            r += x;
        }
        while (l < r) {
            int mid = (l + r) >> 1;
            if (f(nums, mid) >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }

    private int f(int[] nums, int s) {
        int t = 0, j = 0;
        int cnt = 0;
        for (int i = 0; i < nums.length; ++i) {
            t += nums[i];
            while (t > s) {
                t -= nums[j++];
            }
            cnt += i - j + 1;
        }
        return cnt;
    }
}

  • class Solution {
public:
    int kthSmallestSubarraySum(vector<int>& nums, int k) {
        int l = 1 << 30, r = 0;
        for (int& x : nums) {
            l = min(l, x);
            r += x;
        }
        auto f = [&](int s) {
            int cnt = 0, t = 0;
            for (int i = 0, j = 0; i < nums.size(); ++i) {
                t += nums[i];
                while (t > s) {
                    t -= nums[j++];
                }
                cnt += i - j + 1;
            }
            return cnt;
        };
        while (l < r) {
            int mid = (l + r) >> 1;
            if (f(mid) >= k) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
};


  • class Solution:
    def kthSmallestSubarraySum(self, nums: List[int], k: int) -> int:
        def f(s):
            t = j = 0
            cnt = 0
            for i, x in enumerate(nums):
                t += x
                while t > s:
                    t -= nums[j]
                    j += 1
                cnt += i - j + 1
            return cnt >= k

        l, r = min(nums), sum(nums)
        return l + bisect_left(range(l, r + 1), True, key=f)


  • func kthSmallestSubarraySum(nums []int, k int) int {
	l, r := 1<<30, 0
	for _, x := range nums {
		l = min(l, x)
		r += x
	}
	f := func(s int) (cnt int) {
		t := 0
		for i, j := 0, 0; i < len(nums); i++ {
			t += nums[i]
			for t > s {
				t -= nums[j]
				j++
			}
			cnt += i - j + 1
		}
		return
	}
	for l < r {
		mid := (l + r) >> 1
		if f(mid) >= k {
			r = mid
		} else {
			l = mid + 1
		}
	}
	return l
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

All Problems

All Solutions