Solve array and list algorithms
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### 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/
Quick Answer: This question evaluates proficiency in array and list algorithms, including ordering and counting techniques for relative element ranking, merging multiple sorted inputs, and algorithmic design for a package locker retrieval operation, testing data structure manipulation and retrieval logic.
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
Solution
from typing import List
def count_smaller(nums: List[int]) -> List[int]:
n = len(nums)
if n == 0:
return []
# Coordinate compression
values = sorted(set(nums))
idx = {v: i + 1 for i, v in enumerate(values)} # 1-based indices for BIT
# Fenwick Tree (Binary Indexed Tree)
size = len(values)
bit = [0] * (size + 1)
def update(i: int, delta: int) -> None:
while i <= size:
bit[i] += delta
i += i & -i
def query(i: int) -> int:
s = 0
while i > 0:
s += bit[i]
i -= i & -i
return s
res = [0] * n
# Iterate from right to left
for i in range(n - 1, -1, -1):
compressed = idx[nums[i]]
# Count of values strictly less than nums[i]
res[i] = query(compressed - 1)
update(compressed, 1)
return res
Explanation
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).
Hints
- Process elements from right to left while maintaining counts of seen values.
- Use coordinate compression to map values into a dense range.
- Maintain a Binary Indexed Tree (Fenwick Tree) to get prefix sums and update counts in O(log U).
- Alternatively, a modified merge sort can count smaller-on-right during merging.