Posted on by seeker

LeetCode – 561 : Array Partition I

Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.

Example 1:

Input: [1,4,3,2]

Output: 4
Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).

Note:

  1. n is a positive integer, which is in the range of [1, 10000].
  2. All the integers in the array will be in the range of [-10000, 10000].

Idea – 1

The maximum element will not contribute towards the sum. The best pairing with the max elements will be with the second max. Once this pair is determined, we keep doing the same for the array of size n-2. We sort. Time complexity O(n\cdot \lg{n}) and space complexity O(1). 
[code lang="java"]
class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i < n; i += 2)
        {
            sum += nums[i];
        }
        
        return sum;
    }
}
[code]

Runtime: 14 ms, faster than 92.53% of Java online submissions for Array Partition I.Memory Usage: 39.3 MB, less than 99.91% of Java online submissions for Array Partition I.

Posted on by seeker

LeetCode – 88 : Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

  • The number of elements initialized in nums1 and nums2 are m and n respectively.
  • You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6],       n = 3

Output: [1,2,2,3,5,6]
[code lang="java"]
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        
    }
}
[code]

Idea – 1

We start with m-1 th and n-1 th elements from nums1 and nums2, whichever is bigger (say nums2) we put that at m+n-1 th place of nums1 and move leftwards in nums2. If we are done processing nums2, we are done. If we are done with nums1 elements, we copy rest of nums2 to the places left in nums1. Time complexity is O(m+n) and space complexity is O(1). 
[code lang="java"]
class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m-1, j = n-1;
        int k = m+n-1;
        
        while(i >= 0 || j >= 0)
        {
            if(j < 0)
            {
                break;
            }
            else if(i < 0 || nums2[j] >= nums1[i])
            {
                nums1[k--] = nums2[j--];
            }
            else
            {
                nums1[k--] = nums1[i--];
            }
        }
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Merge Sorted Array.Memory Usage: 35.5 MB, less than 99.61% of Java online submissions for Merge Sorted Array.

Posted on by seeker

LeetCode – 215 : Kth Largest Element in an Array

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note: 
You may assume k is always valid, 1 ≤ k ≤ array’s length.

[code lang="java"]
class Solution {
    public int findKthLargest(int[] nums, int k) {
        
    }
}
[code]

Idea – 1

Sort in non-increasing order and return the k-th element. Time and space complexity are that of a comparison based sorting. With traditional mergesort time is O(n\lg{n}) ans space is be O(n). With quicksort average time is O(n\lg{n}) and average space is O(lg{n}). With heapsort time is O(n\lg{n}) and space is O(1). 
[code lang="java"]

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        Integer[] boxedArray = new Integer[n];
        for(int i = 0; i < n; ++i)
        {
            boxedArray[i] = nums[i];
        }
        
        Arrays.sort(boxedArray, (a, b) -> (b - a));
        
        return boxedArray[k-1];
    }
}
[code]

Runtime: 41 ms, faster than 11.26% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 38 MB, less than 62.44% of Java online submissions for Kth Largest Element in an Array.

Idea – 2

We use quickselect: repeatedly partition the array around a random pivot and go right or left based on the rank of the pivot. Average time O(n) and average space O(\lg{n}). Worst case time is O(n^2) and worst case space is O(n). 
[code lang="java"]
class Solution {
    
    private static final Random rng = new Random(System.currentTimeMillis() % Integer.MAX_VALUE);
    
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        
        return partition(nums, 0, n-1, k);
    }
    
    private void swap(int[] A, int i, int j)
    {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
    
    private int partition(int[] A, int lo, int hi, int k)
    {
        int z = lo+rng.nextInt(hi-lo+1);
        int pivot = A[z];
        int i = lo-1, x = lo, j = hi;
        while(x <= j)
        {
            if(A[x] < pivot)
            {
                swap(A, ++i, x++);
            }
            else if(A[x] > pivot)
            {
                swap(A, x, j--);
            }
            else
            {
                ++x;
            }
        }
        
        // (i+1) is where pivot is right now
        int rank = A.length-(i+1);
        
        if(rank==k)
        {
            return pivot;
        }
        else if(rank < k)
        {
            return partition(A, lo, i, k);
        }
        else
        {
            return partition(A, i+2, hi, k);
        }
    }
}
[code]

Runtime: 1 ms, faster than 99.81% of Java online submissions for Kth Largest Element in an Array.Memory Usage: 35.6 MB, less than 97.57% of Java online submissions for Kth Largest Element in an Array.

Posted on by seeker

LeetCode – 33 : Search in Rotated Sorted Array

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

Input: nums = [4,5,6,7,0,1,2], target = 0 
Output: 4

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 
Output: -1
[code lang="java"]
class Solution {
    public int search(int[] nums, int target) {
        
    }
}
[code]

Idea – 1

There are no duplicates. So, after rotation the single sorted array breaks into two sorted arrays separated by a break. We do modified binary search, deciding to go left or right but we need to consider cases when mid is to the left or to the right of the break. Time complexity is O(\lg{n}) and space is O(1). 
[code lang="java"]
class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        while(lo <= hi)
        {
            int mid = lo + (hi-lo)/2;
            
            if(target == nums[mid])
            {
                return mid;
            }
            else if(nums[mid] > nums[hi]) // mid is to the left of break
            {
                if(target >= nums[lo] && target < nums[mid]) // target is between lo and mid
                {
                    // go left
                    hi = mid-1;
                }
                else
                {
                    // go right
                    lo = mid+1;
                }
            }
            else // mid is to the right of break;
            {
                if(target > nums[mid] && target <= nums[hi]) // target is between mid and hi
                {
                    // go right
                    lo = mid+1;
                }
                else
                {
                    // go left
                    hi = mid-1;
                }
            }
        }
        
        return -1;
    }
}
[code]

Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 38.9 MB, less than 75.56% of Java online submissions for Search in Rotated Sorted Array.