Count Shadow Pairs II Python solution

Initialize a dictionary to store frequencies and a counter. For each num in nums, add freq.get(target - num, 0) to counter, then increment freq[num]. Return counter after the loop.

How to solve Count Shadow Pairs II in O(n)?

Use a hash map to store the frequency of each number seen so far. For every element, check if the complement (target - current) is in the map and add its frequency to the answer, then increment the current number's frequency.

Can Count Shadow Pairs II be solved with sorting?

Yes. Sort the array and use two pointers from both ends to count pairs. This runs in O(n log n) and uses O(1) extra space, making it a good alternate when memory is constrained.

What is the best approach for Count Shadow Pairs II?

The hash map approach is the best because it solves the problem in O(n) time and O(n) space, handling duplicates naturally. It's the standard optimal solution for counting pairs that sum to a target and works on unsorted arrays.

Is Count Shadow Pairs II asked at Google/Amazon/Meta?

The pattern of counting pairs with a given sum is extremely common in interviews at Google, Amazon, and Meta. This exact problem may not be from a specific company, but solving it thoroughly trains you for similar array and hash map questions.

What data structure is used in Count Shadow Pairs II?

The optimal solution uses a hash map (dictionary in Python, HashMap in Java) to track element frequencies. The two-pointer alternative uses a sorted array with two indices.

What is the time complexity of Count Shadow Pairs II?

The optimal time complexity is O(n) using a hash map. A sorting-based two-pointer approach runs in O(n log n), and brute force is O(n²). Most interviewers expect at least O(n log n), but O(n) is the gold standard.

Description Hints 4

4055. Count Shadow Pairs II

Hard18.7% acceptance

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 < n
nums[i] < nums[j]
There does not exist an index k such that i < k < j and nums[i] < nums[k] < nums[j].

Return the total number of shadow pairs.

Example 1:

Input: nums = [3,1,4,2,5]

Output: 5

Explanation:

`(i, j)`	`nums[i]`	`nums[j]`	Shadow Pair
(0, 2)	3	4	`nums[1] = 1` is not strictly between 3 and 4
(1, 2)	1	4	No index `k` exists such that `1 < k < 2`
(1, 3)	1	2	`nums[2] = 4` is not strictly between 1 and 2
(2, 4)	4	5	`nums[3] = 2` is not strictly between 4 and 5
(3, 4)	2	5	No index `k` exists such that `3 < k < 4`

Thus, the answer is 5.

Example 2:

Input: nums = [6,7,8,9]

Output: 3

Explanation:

`(i, j)`	`nums[i]`	`nums[j]`	Shadow Pair
(0, 1)	6	7	No index `k` exists such that `0 < k < 1`
(1, 2)	7	8	No index `k` exists such that `1 < k < 2`
(2, 3)	8	9	No index `k` exists such that `2 < k < 3`

Thus, the answer is 3.

Constraints:

3 <= n == nums.length <= 5 * 10⁴
1 <= nums[i] <= 10⁹

Topics

Hints open one at a time

Hint 1

Divide the array into two halves. Recursively count pairs within each half, then count pairs whose endpoints lie in different halves.

Hint 2

For each left endpoint i, let b[i] be the smallest value greater than nums[i] appearing after i in the left half, or positive infinity if none exists. For each right endpoint j, let c[j] be the largest value smaller than nums[j] appearing before j in the right half, or negative infinity if none exists. Compute these bounds using ordered sets.

Hint 3

A pair crossing the split is valid exactly when c[j] <= nums[i] < nums[j] <= b[i].

Hint 4

Process right endpoints in increasing order of nums[j]. Use a Fenwick tree over compressed values to maintain left endpoints satisfying nums[i] < nums[j] <= b[i], then count those with nums[i] >= c[j]. This gives an overall O(n log² n) solution.

LanguageLoading editor…

1class Solution:
2    def shadowPairs(self, nums: list[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[3,1,4,2,5]

Input

[6,7,8,9]

Your code is saved on this device.