One of the sorting algorithms with time complexity of O(nlogn) where n is the length of the given array.
///tc : O(nlogn) //sc : O(n) for creating intermediate arrays a, b of size of part of subarray which is of size n class Solution { public int[] sortArray(int[] nums) { merge(0,nums.length-1,nums); return nums; } public void merge(int start, int end, int arr[]){ if(end>start){ int mid = (start+end)/2; merge(start,mid,arr); merge(mid+1,end,arr); sort(start, mid,end, arr); } } public void sort(int start, int mid ,int end, int arr[]){ int a[] = new int[mid-start+1]; int b[] = new int[end-mid]; for(int i = 0;i< a.length;i++){ a[i] = arr[start+i]; } for(int i= 0;i<b.length;i++){ b[i] = arr[mid+1+i]; } int i = 0; int j =0; int k = start; while(i<a.length && j < b.length){ if(a[i] < b[j]){ arr[k] = a[i++]; } else{ arr[k] = b[j++]; } k++; } while(i<a.length){ arr[k++] = a[i++]; } while(j<b.length){ arr[k++] = b[j++]; } } } How many comparison are needed before the arrays becomes sorted ( given index i, j of array arr[] , arr[i]> arr[j] ( for j> i) will increment the inversion count by 1 every time this condition is met.
note: we can use the same merge sort approach to find the inversion count ( merge sort code have been changed a bit to make it more readable)
class Solution { // arr[]: Input Array // N : Size of the Array arr[] // Function to count inversions in the array. static long inversionCount(long arr[], int n) { // Your Code Here //we can use merge sort long temp[]= new long[n]; return merge(0,n-1,arr,temp); } public static long merge(int start, int end, long arr[],long[] temp){ long count = 0; if(end>start){ int mid = (start+end)/2; count+=merge(start,mid,arr,temp); count+=merge(mid+1,end,arr,temp); count+=sort(start, mid,end, arr,temp); } return count; } public static long sort(int start, int mid ,int end, long arr[],long [] temp){ long count = 0; int i = start; int j = mid+1; int k = start; while(i<=mid && j <=end){ if(arr[i]<=arr[j]){ temp[k] = arr[i++]; } else{ temp[k] = arr[j++]; count+= mid-i+1; // if ( a[i] > arr[j] then all the values after ith index including will be // greater that jth index value hence count += mid-i+1 } k++; } while(i<=mid){ temp[k++] = arr[i++]; } while(j<=end){ temp[k++] = arr[j++]; } for(int l = start;l<=end;l++){ arr[l] = temp[l]; } return count; } } Note: This is based on Kadane's algorithm of finding the subarray maximum sum
//tc :O(n) where n is the length of the given array class Solution { public int maxSubArray(int[] nums) { int max = Integer.MIN_VALUE; int sum = 0; for(int i =0;i<nums.length;i++){ sum+=nums[i]; if(sum > max){ max = sum; } if(sum<0) sum = 0; } return max; } } - We have to make sure that duplicates are avoided, hence we to ignore
nums[prev] == nums[current]thencurrentindex value needs to be avoided.
Note: We can use the same approach for 2 sum or 4 sum problems
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> list = new ArrayList<>(); int n = nums.length; Arrays.sort(nums); for(int i =0;i<n;i++){ if(i>0 && nums[i] ==nums[i-1]) continue; int j = i+1; int k = n-1; while(j<k){ int sum = nums[i] + nums[j] + nums[k]; if(sum ==0){ List<Integer> l = new ArrayList<>(); l.add(nums[i]); l.add(nums[j]); l.add(nums[k]); list.add(l); k--; j++; while(j<k && nums[k] ==nums[k+1]) k--; while(j<k && nums[j] == nums[j-1]) j++; } else if(sum > 0) k--; else j++; } } return list; } } 
Top comments (0)