How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a hard difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Meta.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Meta during technical interviews.

Solve Subarray Sum and Local Minimum

Quick Overview

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.

Loading coding console...

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

Input: ([9],)

Expected Output:

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

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

Expected Output:

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

Input: ([5, 4, 3, 2, 1],)

Expected Output:

Explanation: The array is strictly decreasing, so the last element is the only local minimum.

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

Expected Output:

Explanation: The array is strictly increasing, so the first element is the only local minimum.

Input: ([9, 7, 3, 4, 8],)

Expected Output:

Explanation: nums[2] = 3 is smaller than both 7 and 4, so index 2 is a local minimum.

Hints

First check the boundary cases: the first or last element may already be a local minimum.
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.

Quick Overview