K’th Largest Element in Unsorted Array

Given an array and a number k where k is smaller than size of array, find the k’th largest element in the given array. All array elements are distinct.

Examples:

Input: arr[] = {1, 7, 10, 4, 3, 30, 15}
       k = 3
Output: 10

Input: arr[] = {1, 7, 10, 4, 3, 30}
       k = 4
Output: 4

Java (sorting)
Time complexity: O(N log N)
Space complexity: O(1)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        Arrays.sort(nums);
        
        return nums[nums.length-k];
        
    }
}

Java (heap sort)
Time complexity: O(N log N)
Space complexity: O(N)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        Queue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
        for (int n : nums){
            q.offer(n);
        }
        
        for (int i = 1; i < k; ++i){
            q.poll();
        }
        
        return q.poll();
        
    }
}

Java (quick select)
Time complexity: O(N)
Space complexity: O(N)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0 || k > nums.length) {
            return -1;
        }

        //shuffle to eliminate worst case running time O(N^2)
        shuffle(nums);

        return findKthLargest(nums, k, 0, nums.length - 1);

    }

    private int findKthLargest(int[] nums, int k, int lo, int hi){
       if (lo <= hi){
            int pivot = partition(nums, lo, hi);

            if (hi - pivot == k - 1){
                return nums[pivot];
            } else if (hi - pivot < k - 1){
                return findKthLargest(nums,k-(hi-pivot+1),lo, pivot - 1);
            } else {
                return findKthLargest(nums,k,pivot + 1, hi);
            }
        }

        return -1;
    }

    private int partition(int[] nums, int lo, int hi){
        if (lo <= hi){
            int i = lo + 1;
            int j = lo + 1;

            while (j <= hi){
                if (nums[j] < nums[lo]){
                    swap(i, j, nums);
                    ++i;
                }
                 ++j;
            }

            swap(lo, i-1, nums);
            return i-1;
        }
        return -1;
    }

    private void shuffle(int[] nums){
        Random r = new Random();
        for (int i = 1; i < nums.length; ++i){
            int j = r.nextInt(i+1);
            swap(i, j, nums);
        }

    }


    private void swap(int i, int j, int[] nums){
        int x = nums[i];
        x ^= nums[j];
        nums[j] = x ^ nums[j];
        nums[i] = x ^ nums[j];
    }
}
Advertisements

Lintcode. Number of Airplanes in the Sky

Given an interval list which are flying and landing time of the flight. How many airplanes are on the sky at most?

Notice

If landing and flying happens at the same time, we consider landing should happen at first.

 

Java
Time complexity: O(N log N)
Space complexity: O(N)

class Solution {
    /**
     * @param intervals: An interval array
     * @return: Count of airplanes are in the sky.
     */
    public int countOfAirplanes(List<Interval> airplanes) { 
        // write your code here
        if (airplanes == null || airplanes.size() == 0){
            return 0;
        }
        
        int n = airplanes.size();
        int[] start = new int[n];
        int[] land = new int[n];
        
        for (int i = 0; i < n; ++i){
            Interval t = airplanes.get(i);
            start[i] = t.start;
            land[i] = t.end;
        }
        
        Arrays.sort(start);
        Arrays.sort(land);
        
        int maxPlanes = Integer.MIN_VALUE;
        int currPlanes = 0;
        
        int startPtr = 0;
        int landPtr = 0;
        
        while (startPtr < n){
            if (land[landPtr] <= start[startPtr]){
                currPlanes -= 1;
                ++landPtr;
            } else if (start[startPtr] < land[landPtr]){
                currPlanes += 1;
                ++startPtr;    
            } 
            maxPlanes = Math.max(maxPlanes, currPlanes);
        }
        
        return maxPlanes;
        
        
    }
}

Python
Time complexity: O(N log N)
Space complexity: O(N)

class Solution:
    # @param airplanes, a list of Interval
    # @return an integer
    def countOfAirplanes(self, airplanes):
        # write your code here
        if not len(airplanes):
            return 0;
        
        #creates copy of iterable, one may use [].sort() instead   
        start = sorted([plane.start for plane in airplanes])
        land = sorted([plane.end for plane in airplanes])
        
        maxAirplanes = 0
        currAirplanes = 0
        sIdx = 0
        lIdx = 0
        
        while sIdx < len(airplanes):
            if start[sIdx] < land[lIdx]:
                currAirplanes += 1
                sIdx += 1
            else:
                currAirplanes -= 1
                lIdx += 1
                
            maxAirplanes = max(maxAirplanes, currAirplanes)
        
            
        return maxAirplanes;

Leetcode. Find All Duplicates in an Array

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]


Java
Time complexity: O(N)
Space complexity: O(1)

public class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        if (nums == null || nums.length == 0){
            return new ArrayList<Integer>();
        }
        List<Integer> res = new ArrayList<Integer>();
        
        for (int n : nums){
            int idx = Math.abs(n);
            if (nums[idx-1] < 0){
                res.add(idx);
            }
            nums[idx-1] = ~nums[idx-1] + 1;
        }
        //restore array
        for (int i = 0; i < nums.length; ++i){
            nums[i] = Math.abs(nums[i]);
        }
        return res;
    }
}

Lintcode. Best Time to Buy and Sell Stock I, II, III

Best Time to Buy and Sell Stock I

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example
Given array [3,2,3,1,2], return 1.

Python
Time complexity: O(N)
Space complexity: O(1)

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        # write your code here
        if (not prices or len(prices) <= 1):
            return 0
            
        minSoFar = prices[0]
        profit = 0
        
        for v in prices[1:]:
            minSoFar = min(minSoFar, v)
            profit = max(profit, v - minSoFar)

        return profit

 

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example
Given an example [2,1,2,0,1], return 2.

Java
Time complexity: O(N)
Space complexity: O(1)

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     * As a solution one can find sum of contiguous delta trades, where 
     * 'delta trade' stands for buy-sell compound transaction.
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if (prices == null || prices.length <= 0){
            return 0;
        }
        
        int profit = 0;
        
        for (int i = 1; i < prices.length; ++i){
            profit += Math.max(0, prices[i] - prices[i-1]);
        }
        
        return profit;
    }
}

 

Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Notice : You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Example

Given an example [4,4,6,1,1,4,2,5], return 6.

Java
Time complexity: O(N)
Space complexity: O(1)

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        if (prices == null || prices.length == 0){
            return 0;
        }
        
        int buyFirst = Integer.MIN_VALUE;
        int sellFirst = 0;
        int buySecond = Integer.MIN_VALUE;
        int sellSecond = 0;
        
        for (int i = 0; i < prices.length; ++i){
            buyFirst = Math.max(buyFirst, -prices[i]);
            sellFirst = Math.max(buyFirst + prices[i], sellFirst);
            buySecond = Math.max(buySecond, sellFirst - prices[i]);
            sellSecond = Math.max(sellSecond, buySecond + prices[i]);
        }
        
        return sellSecond;
    }
}

Lintcode. Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

Example

Given the following matrix:

[

 [ 1, 2, 3 ],

 [ 4, 5, 6 ],

 [ 7, 8, 9 ]

]

You should return [1,2,3,6,9,8,7,4,5].

 

Java
Time complexity: O(N*M), N – num of rows, M – num of columns
Space complexity: O(N*M), N – num of rows, M – num of columns

public class Solution {
    /**
     * @param matrix a matrix of m x n elements
     * @return an integer list
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        // Write your code here
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0){
            return new ArrayList<>();
        }
        
        int nRow = matrix.length;
        int nCol = matrix[0].length;
        
        List<Integer> res = new ArrayList<>();
        int lvlNum = Math.min(nRow, nCol) / 2 + (Math.min(nRow,nCol) % 2 > 0 ? 1 : 0);

        
        for (int level = 0; level < lvlNum; ++level){
            for (int col = level; col < nCol - level; ++col){
                res.add(matrix[level][col]);
            }
            for (int row = level + 1; row < nRow - level; ++row){
                res.add(matrix[row][nCol-level-1]);
            }
            if (nRow-level-1 == level){//avoid row overlap
                break;
            }
            for (int col = nCol - level - 2; col >= level; --col){
                res.add(matrix[nRow-level-1][col]);
            }
            if (level == nCol-level-1){//avoid column overlap
                break;    
            }
            for (int row = nRow-level-2; row > level; --row){
                res.add(matrix[row][level]);
            }
        }
        
        return res;
    }
}