cswork / libraryOpen practice workspace

Coding questions · Meta

Solve Subarray Sum and Local Minimum

This question evaluates array algorithm proficiency and complexity analysis by testing the ability to count target-sum contiguous subarrays and to locate a local minimum under a logarithmic-time constraint. It is commonly asked in the Coding & Algorithms domain to measure practical implementation skills and conceptual understanding of algorithmic patterns and time-complexity guarantees.

Two coding problems were reported in the same phone-screen round:

  1. Count target-sum subarrays. Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum is exactly k.

  2. Find any local minimum in O(log n). Given an array nums of length n >= 1 where every pair of adjacent elements is different, return any index i such that nums[i] is a local minimum:

    • i = 0 is valid if nums[0] < nums[1]
    • i = n - 1 is valid if nums[n - 1] < nums[n - 2]
    • otherwise, i is valid if nums[i] < nums[i - 1] and nums[i] < nums[i + 1]

The required time complexity for the second problem is O(log n).

Part 1: Count Target-Sum Subarrays

Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum is exactly k. A subarray is a continuous block of elements in the array. The array may contain positive numbers, negative numbers, and zeros.

Constraints

  • 0 <= len(nums) <= 200000
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= k <= 10^9

Examples

Example 1

Input: ([1, 1, 1], 2)
Output: 2

Explanation: The subarrays [1, 1] at indices (0..1) and (1..2) both sum to 2.

Example 2

Input: ([1, 2, 3], 3)
Output: 2

Explanation: The valid subarrays are [1, 2] and [3].

Hints

  1. Think about prefix sums: if prefix_sum[j] - prefix_sum[i] == k, then the subarray (i+1..j) has sum k.
  2. Use a hash map to count how many times each prefix sum has appeared so far.

Part 2: Find Any Local Minimum in O(log n)

Given an array nums of length n >= 1 where every pair of adjacent elements is different, return any index i such that nums[i] is a local minimum.

An index i is a local minimum if:

  • i == 0 and nums[0] < nums[1], or
  • i == n - 1 and nums[n - 1] < nums[n - 2], or
  • 0 < i < n - 1 and nums[i] < nums[i - 1] and nums[i] < nums[i + 1]

Your algorithm must run in O(log n) time.

Constraints

  • 1 <= len(nums) <= 200000
  • -10^9 <= nums[i] <= 10^9
  • nums[i] != nums[i + 1] for all 0 <= i < n - 1

Examples

Example 1

Input: ([9],)
Output: 0

Explanation: With one element, index 0 is trivially a local minimum.

Example 2

Input: ([2, 1, 3],)
Output: 1

Explanation: nums[1] = 1 is smaller than both neighbors.

Hints

  1. First check the boundary cases: the first or last element may already be a local minimum.
  2. During binary search, if nums[mid] is greater than its left neighbor, then a local minimum must exist on the left side; otherwise it must exist on the right side.