The problem can be found at the following link: Problem Link
✨ LeetCode Problem of the Day (POTD) Started ✨
As promised in the poll, I’ve started solving and uploading LeetCode Problem of the Day (POTD) solutions! 🎯
Problem DescriptionGiven an array of integers arr[]. Find the Inversion Count in the array.Two elements arr[i] and arr[j] form an inversion if arr[i] > arr[j] and i < j.Inversion Count indicates how far (or close) the array is from being sorted:If the array is already sorted, the inversion count is 0.If the array is sorted in reverse order, the inversion count is maximum.Examples:Input:
arr[] = [2, 4, 1, 3, 5]
Output:
3Explanation:
The sequence 2, 4, 1, 3, 5 has three inversions: (2, 1), (4, 1), (4, 3).Input:
arr[] = [2, 3, 4, 5, 6]
Output:
0Explanation:
The array is already sorted, so there are no inversions.Input:
arr[] = [10, 10, 10]
Output:
0Explanation:
All elements of the array are the same, so there are no inversions.Constraints:$1 ≤ arr.size() ≤ 10^5$$1 ≤ arr[i] ≤ 10^4$My ApproachMerge Sort-Based Counting:The problem can be efficiently solved using a modified Merge Sort algorithm.During the merge step, count the number of inversions based on the positions of elements in the two halves.Steps:Divide: Recursively divide the array into two halves.Merge: Merge the two halves while counting inversions.Count Inversions: For every pair (i, j) where arr[i] > arr[j] and i < j, increment the count.Advantages:This approach efficiently counts inversions with a time complexity of O(n log n), compared to the naive O(n^2) method.Time and Auxiliary Space ComplexityExpected Time Complexity: O(n log n), as the algorithm performs a logarithmic number of merge steps, with each step taking linear time.Expected Auxiliary Space Complexity: O(n), as we use an additional array for temporary storage during the merge process.Code (C)int mergeAndCount(int arr[], int temp[], int left, int mid, int right) { int i = left, j = mid + 1, k = left, inversions = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inversions += (mid - i + 1); } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inversions;}int mergeSortAndCount(int arr[], int temp[], int left, int right) { int inversions = 0; if (left < right) { int mid = left + (right - left) / 2; inversions += mergeSortAndCount(arr, temp, left, mid); inversions += mergeSortAndCount(arr, temp, mid + 1, right); inversions += mergeAndCount(arr, temp, left, mid, right); } return inversions;}int countInversions(int arr[], int n) { int temp[n]; return mergeSortAndCount(arr, temp, 0, n - 1);}Code (Cpp)class Solution {public: int mergeAndCount(vector<int>& arr, int left, int mid, int right) { int i = left, j = mid + 1, k = 0, inversions = 0; vector<int> temp(right - left + 1); while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inversions += (mid - i + 1); } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left, k = 0; i <= right; ++i, ++k) { arr[i] = temp[k]; } return inversions; } int mergeSortAndCount(vector<int>& arr, int left, int right) { int inversions = 0; if (left < right) { int mid = left + (right - left) / 2; inversions += mergeSortAndCount(arr, left, mid); inversions += mergeSortAndCount(arr, mid + 1, right); inversions += mergeAndCount(arr, left, mid, right); } return inversions; } int inversionCount(vector<int>& arr) { return mergeSortAndCount(arr, 0, arr.size() - 1); }};Code (Java)class Solution { private int mergeAndCount(int[] arr, int[] temp, int left, int mid, int right) { int i = left, j = mid + 1, k = left, inversions = 0; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inversions += (mid - i + 1); } } while (i <= mid) temp[k++] = arr[i++]; while (j <= right) temp[k++] = arr[j++]; for (i = left; i <= right; i++) { arr[i] = temp[i]; } return inversions; } private int mergeSortAndCount(int[] arr, int[] temp, int left, int right) { int inversions = 0; if (left < right) { int mid = left + (right - left) / 2; inversions += mergeSortAndCount(arr, temp, left, mid); inversions += mergeSortAndCount(arr, temp, mid + 1, right); inversions += mergeAndCount(arr, temp, left, mid, right); } return inversions; } public int inversionCount(int[] arr) { int[] temp = new int[arr.length]; return mergeSortAndCount(arr, temp, 0, arr.length - 1); }}Code (Python)class Solution: def mergeAndCount(self, arr, temp, left, mid, right): i, j, k = left, mid + 1, left inversions = 0 while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] j += 1 inversions += (mid - i + 1) k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 for i in range(left, right + 1): arr[i] = temp[i] return inversions def mergeSortAndCount(self, arr, temp, left, right): inversions = 0 if left < right: mid = left + (right - left) // 2 inversions += self.mergeSortAndCount(arr, temp, left, mid) inversions += self.mergeSortAndCount(arr, temp, mid + 1, right) inversions += self.mergeAndCount(arr, temp, left, mid, right) return inversions def inversionCount(self, arr): n = len(arr) temp = [0] * n return self.mergeSortAndCount(arr, temp, 0, n - 1)Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: Any Questions. Let’s make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
