Inversion count and LCS
Filed under Amazon
Free read 3 of 3Understand inputs, output formats, and performance constraints to avoid recursion limits.
The question
Given an array of integers, find its inversion count (number of pairs (i, j) such that i < j and arr[i] > arr[j]). Additionally, find the length of the Longest Common Subsequence (LCS) of two given strings.
Constraints
- Array length up to 10^5
- String lengths up to 1000
- Avoid recursive solutions
Examples
- Input
- arr = [2, 4, 1, 3, 5], text1 = "abcde", text2 = "ace"
- Output
- Inversions = 3, LCS = 3
- Why
- Inversion pairs are (2,1), (4,1), (4,3). LCS is "ace" of length 3.
Approach
Understand inputs, output formats, and performance constraints to avoid recursion limits.
Check all pairs for inversions (O(n^2)) and use nested loops or recursion for LCS.
Use a modified Merge Sort to count inversions in O(n log n). Use dynamic programming with a 2D table or rolling arrays for LCS in O(m * n) time and O(min(m, n)) space.
Empty arrays/strings, duplicate elements, and arrays sorted in reverse order.
Tips
- What they are testing: Test with strictly increasing/decreasing arrays and completely disjoint strings.
- Common mistake: Using naive O(n^2) nested loops for inversion counting instead of modified merge sort.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.