O(n log n)

Everything about O(n log n)

1. Article · Java

   Dominant Pairs — Sorting and Two-Pointer Approach in Java

   Given an even-sized integer array, divide the array into two equal halves. A pair (i, j) is considered a dominant pair if i belongs to the first half, j belongs to the second half, and arr[i] >= 5 × arr[j]. The goal is to count the total number of dominant pairs efficiently. A brute-force approach takes O(n²) time. By sorting both halves independently and using the two-pointer technique, we can solve the problem in O(n log n) time. This problem is a good example of how sorting can optimize pair-counting problems by avoiding unnecessary comparisons.

   Sandhiya PriyaSep 162,0751,000