Sorting an array based on another array's order is a popular coding problem seen in interviews and real-world systems where custom sorting logic is required.
๐งฉ Problem Statement
You're given two arrays:
-
arr1: The array you need to sort. -
arr2: Specifies the relative ordering of some elements.
๐ Sort Rules:
-
Elements from
arr1that are inarr2appear first, in the same order as inarr2. -
Remaining elements (not in
arr2) are sorted in ascending order.
✅ Example
Input:
arr1 = [2,3,1,3,2,4,6,7,9,2,19]
arr2 = [2,1,4,3,9,6]
Output:
[2,2,2,1,4,3,3,9,6,7,19]
๐งช Approach 1: Counting Sort (Optimal if Range is Known)
✅ Code:
public int[] relativeSortArray(int[] arr1, int[] arr2) {
int[] count = new int[1001]; // assume elements are in 0–1000 range
for (int num : arr1) count[num]++;
int[] result = new int[arr1.length];
int i = 0;
for (int num : arr2)
while (count[num]-- > 0)
result[i++] = num;
for (int num = 0; num < count.length; num++)
while (count[num]-- > 0)
result[i++] = num;
return result;
}
✅ When to Use:
-
You know the range of input (e.g., 0 to 1000).
-
Performance is critical (time complexity: O(n + m + k)).
-
Memory usage is acceptable for fixed range.
๐ง Tips:
-
Preallocate frequency arrays if range is predictable.
-
Avoid using this for values outside a known range (e.g., negative numbers, large integers).
๐ Approach 2: Java 8 Functional Solution (Elegant & Flexible)
✅ Code:
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int[] relativeSortArray(int[] arr1, int[] arr2) {
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < arr2.length; i++) indexMap.put(arr2[i], i);
List<Integer> list = Arrays.stream(arr1).boxed().collect(Collectors.toList());
list.sort((a, b) -> {
if (indexMap.containsKey(a) && indexMap.containsKey(b))
return Integer.compare(indexMap.get(a), indexMap.get(b));
else if (indexMap.containsKey(a))
return -1;
else if (indexMap.containsKey(b))
return 1;
else
return Integer.compare(a, b);
});
return list.stream().mapToInt(Integer::intValue).toArray();
}
}
✅ When to Use:
-
You want a cleaner, more readable solution.
-
The input range is unknown or unbounded.
-
You’re working in a modern Java codebase that uses Streams and Lambdas.
๐ง Best Practices & Tips
| Practice | Tip |
|---|---|
| ๐ข Choose Right Approach | Use counting sort for known integer ranges. Use Java 8 functional approach for readability and flexibility. |
| ♻️ Avoid Magic Numbers | Use Integer.MAX_VALUE or define range constants instead of hardcoding 1001. |
| ๐ Handle Edge Cases | Always account for: duplicates, missing values in arr2, or values in arr2 not present in arr1. |
| ⚙️ Immutable Data | Prefer working with immutable streams when functional clarity matters. |
| ๐ Convert Safely | Use boxed() and mapToInt() to safely convert between primitives and wrappers. |
| ๐ Optimize for Large Input | Counting sort is more performant than stream sorting when input size is large and value range is small. |
| ๐งช Unit Testing | Cover edge cases like arr2 being empty, all values in arr1 being outside arr2, etc. |
๐ Summary
| Feature | Counting Sort | Java 8 Functional |
|---|---|---|
| Input Range Required | ✅ Yes (e.g., 0–1000) | ❌ No |
| Duplicates | ✅ Handled | ✅ Handled |
| Readability | ❌ Medium | ✅ High |
| Performance | ✅ Faster for small range | ❌ Slightly Slower |
| Suitable for Interviews | ✅ Yes | ✅ Yes (bonus if explained well) |
๐ง๐ป Final Thoughts
Both approaches are valid and useful depending on your context:
-
For interview coding rounds, start with the counting sort for performance, then mention the Java 8 version as a cleaner alternative.
-
For production code, prefer the Java 8 solution unless performance is critical and the input range is tightly controlled.
