Count Shadow Pairs I solution and explanation
3 more videos on this problem
Leetcode 4054 | Count Shadow Pairs I | Leetcode weekly contest 519CodeWithMeGuys · 14:05 · 827 views
Count Shadow Pairs I | Monotonic Stack & Occurrence Binary Search | Leetcode Contest 519Sanyam IIT Guwahati · 20:01 · 398 views
Count Shadow Pairs I | Weekly Contest 519 | LeetCodeaniketdevlp · 16:20 · 34 views
4054. Count Shadow Pairs I (Leetcode Medium)Programming Live with Larry · 14:35 · 14 views
The problem
You are given an integer array nums of length n.
A pair of indices (i, j) is called a shadow pair if all of the following conditions are satisfied:
0 <= i < j < nnums[i] < nums[j]- There does not exist an index
ksuch thati < k < jandnums[k] < nums[i] < nums[j].
Return the total number of shadow pairs.
Example 1:
Input: nums = [3,1,4,1,5]
Output: 3
Explanation:
(i, j) |
nums[i] |
nums[j] |
Shadow Pair |
|---|---|---|---|
| (1, 2) | 1 | 4 | No index k exists such that 1 < k < 2 |
| (1, 4) | 1 | 5 | nums[2] = 4 and nums[3] = 1 are not smaller than 1 |
| (3, 4) | 1 | 5 | No index k exists such that 3 < k < 4 |
Thus, the answer is 3.
Example 2:
Input: nums = [6,7,6,6,7]
Output: 4
Explanation:
(i, j) |
nums[i] |
nums[j] |
Shadow Pair |
|---|---|---|---|
| (0, 1) | 6 | 7 | No index k exists such that 0 < k < 1 |
| (0, 4) | 6 | 7 | nums[1] = 7, nums[2] = 6, and nums[3] = 6 are not smaller than 6 |
| (2, 4) | 6 | 7 | nums[3] = 6 is not smaller than 6 |
| (3, 4) | 6 | 7 | No index k exists such that 3 < k < 4 |
Thus, the answer is 4.
Example 3:
Input: nums = [1,2,3,4]
Output: 6
Explanation:
(i, j) |
nums[i] |
nums[j] |
Shadow Pair |
|---|---|---|---|
| (0, 1) | 1 | 2 | No index k exists such that 0 < k < 1 |
| (0, 2) | 1 | 3 | nums[1] = 2 is not smaller than 1 |
| (0, 3) | 1 | 4 | nums[1] = 2 and nums[2] = 3 are not smaller than 1 |
| (1, 2) | 2 | 3 | No index k exists such that 1 < k < 2 |
| (1, 3) | 2 | 4 | nums[2] = 3 is not smaller than 2 |
| (2, 3) | 3 | 4 | No index k exists such that 2 < k < 3 |
Thus, the answer is 6.
Constraints:
3 <= n == nums.length <= 1051 <= nums[i] <= 109
Approach overview
Problem Overview: You are given an integer array nums. A pair (i, j) is a shadow pair if i < j, nums[i] > nums[j], and every element between i and j is strictly smaller than nums[i]. Think of the left element as a building that casts a shadow to the right; any taller or equal building immediately blocks that shadow. Count how many such pairs exist.
Approach 1: Brute Force (O(n²) Time, O(1) Space)
For each index i, start at j = i + 1 and keep moving right while nums[j] < nums[i]. Every index you pass is a valid shadow pair because every intermediate value is smaller than nums[i]. Stop as soon as you see a value >= nums[i], because that element blocks the shadow and hides everything further right. The worst case is a strictly decreasing array, where every i scans to the end, giving O(n²) total work. This approach uses no extra memory and is useful when n is small, such as n ≤ 1,000.
Approach 2: Monotonic Stack (O(n) Time, O(n) Space)
The key insight is that for each i, you only need to know the first index to the right with nums[k] >= nums[i]. Every index between i and that blocker is automatically a valid shadow pair, and nothing after the blocker can be valid. To find all blockers at once, iterate from right to left and maintain a monotonic stack of indices. While the stack top points to a value smaller than nums[i], pop it; the remaining stack top, if any, is the first blocking index. Add the distance between i and that blocker minus one to the answer, then push i. Because each index is pushed and popped at most once, the total time is O(n). This is the classic next greater element pattern.
Recommended for interviews: Start with brute force to demonstrate that you understand the pair definition. Then switch to the monotonic stack solution to show you recognize how blockers segment the array and that you can apply the next greater-or-equal pattern. Most interviewers expect the O(n) solution; it appears repeatedly in visibility, skyline, and histogram problems, so this pattern is worth mastering.
The written solution for this problem is still being prepared. Try it yourself in the meantime.
Try solving it yourselfComplexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Small arrays or a correctness baseline |
| Monotonic Stack | O(n) | O(n) | Large arrays and interview settings |
Frequently asked questions
Is Count Shadow Pairs I easy or hard?
It is a Medium problem with about 40.6% acceptance. The brute force is easy to understand, but reaching the O(n) monotonic stack solution is what separates a strong performance in interviews.
Count Shadow Pairs I Python/Java solution
Use the same monotonic stack algorithm in Python or Java: loop right-to-left, pop smaller values, add the blocker distance minus one, then push the current index. The solution code for both languages is available on FleetCode.
How to solve Count Shadow Pairs I in O(n)?
Iterate from right to left and maintain a stack of indices with non-increasing heights. While the stack top has a value smaller than the current element, pop it. The remaining stack top is the first blocking index; add the distance to it minus one to the answer.
What is the best approach for Count Shadow Pairs I?
The best approach is a monotonic stack to find the next greater-or-equal element for every index. It runs in O(n) time and O(n) space, counting all valid pairs in a single right-to-left pass.
Is Count Shadow Pairs I asked at Google/Amazon/Meta?
The specific problem may be recent contest material, but the underlying monotonic stack pattern is frequently tested by Amazon, Google, and Meta in questions about visible pairs, next greater element, and histogram area.
What data structure is used in Count Shadow Pairs I?
A monotonic stack is used, specifically a decreasing stack that stores indices by element value. It lets you find the next greater-or-equal element efficiently while iterating the array once.
What is the time complexity of Count Shadow Pairs I?
The brute force solution is O(n²) in the worst case because each index may scan to the end. The optimal monotonic stack solution is O(n) time and O(n) space, since each index is pushed and popped at most once.