Quick Overview

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.

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/

Overview: 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

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.

Loading coding console...

Show the approach

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)