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)