Solve array and list algorithms

Question

LeetCode 315. Count of Smaller Numbers After Self LeetCode 23. Merge k Sorted Lists Design algorithm for Amazon Locker getPackage (retrieve package) operation

https://leetcode.com/problems/count-of-smaller-numbers-after-self/description/ https://leetcode.com/problems/merge-k-sorted-lists/description/

Count Smaller Numbers After Self

Given an integer array nums, for each index i compute how many elements to the right of i have a value strictly less than nums[i]. Return an array of the same length where the i-th value is this count.

Constraints

• 0 <= n <= 200000, where n is len(nums)
• -10^9 <= nums[i] <= 10^9
• Return a list of length n
• Aim for O(n log n) time; O(n) or O(n + U) space (U = number of distinct values) is acceptable

Examples

Example 1

Input: nums = [5,2,6,1]
Output: [2,1,1,0]

Explanation: Right of 5 are [2,6,1] with two smaller (2,1); right of 2 is [6,1] with one smaller (1); right of 6 is [1] with one smaller; right of 1 is [] with zero smaller.

Example 2

Input: nums = [1,2,2,1]
Output: [0,1,1,0]

Explanation: Right of 1 are [2,2,1] with zero smaller; right of first 2 is [2,1] with one smaller (1); right of second 2 is [1] with one smaller; last 1 has none to the right.

Hints

1. Process elements from right to left while maintaining counts of seen values.
2. Use coordinate compression to map values into a dense range.
3. Maintain a Binary Indexed Tree (Fenwick Tree) to get prefix sums and update counts in O(log U).
4. Alternatively, a modified merge sort can count smaller-on-right during merging.

Approach

We traverse nums from right to left, maintaining how many times each value has appeared so far. Because values can be large or negative, we first coordinate-compress them into ranks 1..U where U is the number of distinct values. A Fenwick Tree stores frequency counts of seen ranks. For each nums[i], we query the prefix sum up to rank(nums[i]) - 1 to get the number of strictly smaller elements seen to its right, then update the tree at rank(nums[i]). This yields O(n log U) time and efficient memory usage.

• Time complexity: O(n log U), where U is the number of distinct values
• Space complexity: O(n + U)