Showing posts with label Apple. Show all posts
Showing posts with label Apple. Show all posts

Tuesday, July 11, 2017

36. Valid Sudoku

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.
The Sudoku board could be partially filled, where empty cells are filled with the character '.'.
A partially filled sudoku which is valid.
Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.



Solution:

For this kind of problems, you have to go through the entire grid to check each entry.

We first check each row.

Secondly we check each column.

Finally we check each 3 x 3 grid. We can use / and % to locate the coordinates of sub grid.

The time complexity is O(1) and the space complexity is O(1), since the number of input is constant.



Code:

public class Solution {
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length != 9) {
            return false;
        }
        if (board[0] == null || board[0].length != 9) {
            return false;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int j = 0; j < 9; j++) {
            for (int i = 0; i < 9; i++) {
                if (board[i][j] == '.') {
                    continue;
                }
                if (set.contains(board[i][j])) {
                    return false;
                }
                set.add(board[i][j]);
            }
            set.clear();
        }
        for (int k = 0; k < 9; k++) {
            for (int i = k / 3 * 3; i < k / 3 * 3 + 3; i++) {
                for (int j = (k % 3) * 3; j < (k % 3) * 3 + 3; j++) {
                    if (board[i][j] == '.') {
                        continue;
                    }
                    if (set.contains(board[i][j])) {
                        return false;
                    }
                    set.add(board[i][j]);
                }
            }
            set.clear();
        }
        return true;
    }
}

Monday, June 26, 2017

240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.
For example,
Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]
Given target = 5, return true.
Given target = 20, return false.



Solution:

The row is in ascending order and the column is also in ascending order.

So we can start from the bottom left.

If the target is smaller than the current point, the matching point can only be in the above area.

We go up.

If the target is target than the current point, the matching point can only be int he right area.

We go right.

The time complexity is O(m + n) and the space complexity is O(1).



Code:


public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0) {
            return false;
        }
        if (matrix[0] == null || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        
        int x = m - 1;
        int y = 0;
        while (x >= 0 && x < m && y >= 0 && y < n) {
            if (matrix[x][y] == target) {
                return true;
            }
            else if (matrix[x][y] < target) {
                y++;
            }
            else {
                x--;
            }
        }
        return false;
    }
}

Sunday, June 18, 2017

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.



Solution:

This is a Dynamic Programing problem.

We have 1 way to jump to step 1 and 2 ways to jump to step 2.

The ways to jump to step i is the ways to jump to step i - 1 plus the ways to jump to step i - 2.

In other words, from step i - 1, we have only 1 way to jump to step i, which is to jump 1 step.

From step i - 2, we also have only 1 way to jump to step i, which is to jump 2 steps.

Therefore, dp[i] = dp[i - 1] + dp[i - 2].

We can optimize the space by only use two variables to store the states.



Code:


public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        if (n == 2) {
            return 2;
        }
        int n1 = 1;
        int n2 = 2;
        for (int i = 3; i <= n; i++) {
            int curr = n1 + n2;
            n1 = n2;
            n2 = curr;
        }
        return n2;
    }
}

Saturday, June 10, 2017

207. Course Schedule

There are a total of n courses you have to take, labeled from 0 to n - 1.
Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]
Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?
For example:
2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.
2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.
Note:
  1. The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
  2. You may assume that there are no duplicate edges in the input prerequisites.
Hints:
  1. This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
  2. Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
  3. Topological sort could also be done via BFS.



Solution:

This is a topological order question.

It asks whether the courses can be formed a topological order.

Therefore we use a count variable to store the number of courses that can form such order.

If it equals to the total number of courses, we return true.



Code:


public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] adj = new List[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new ArrayList<Integer>();
        }
        int[] degree = new int[numCourses];
        for (int[] pair : prerequisites) {
            int courseFrom = pair[1];
            int courseTo = pair[0];
            adj[courseFrom].add(courseTo);
            degree[courseTo]++;
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < degree.length; i++) {
            if (degree[i] == 0) {
                queue.offer(i);
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            for (int nei : adj[course]) {
                degree[nei]--;
                if (degree[nei] == 0) {
                    queue.offer(nei);
                }
            }
        }
        return count == numCourses;
    }
}

Sunday, May 28, 2017

221. Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.



Solution:

Method 1: Dynamic Programming

dp[i][j]: max size to form a square from this point as lower right point.

dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]) + 1



Code:


public class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i][j] = matrix[i][j] - '0';
                }
                else if (matrix[i][j] == '0') {
                    dp[i][j] = 0;
                }
                else {
                    dp[i][j] = Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) + 1;
                }
                max = Math.max(max, dp[i][j]);
            }
        }
        return max * max;
    }
}



Method 2: Optimized with rolling array



Code:


public class Solution {
    public int maximalSquare(char[][] matrix) {
        int max = 0;
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) {
            return 0;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[2][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i == 0 || j == 0) {
                    dp[i % 2][j] = matrix[i][j] - '0';
                }
                else if (matrix[i][j] == '0') {
                    dp[i % 2][j] = 0;
                }
                else {
                    dp[i % 2][j] = Math.min(Math.min(dp[(i - 1) % 2][j], dp[i % 2][j - 1]), dp[(i - 1) % 2][j - 1]) + 1;
                }
                max = Math.max(max, dp[i % 2][j]);
            }
        }
        return max * max;
    }
}

Thursday, May 25, 2017

257. Binary Tree Paths

Given a binary tree, return all root-to-leaf paths.
For example, given the following binary tree:
   1
 /   \
2     3
 \
  5
All root-to-leaf paths are:


["1->2->5", "1->3"]



Solution:

Method 1: DFS

We use DFS to traverse the tree and at the same time we maintain a path of values.

When we reach a leaf, we add the current path to the result.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        helper(result, root, "" + root.val);
        return result;
    }
    
    public void helper(List<String> result, TreeNode root, String str) {
        if (root == null) {
            return;
        }
        if (root.left == null && root.right == null) {
            result.add(str);
            return;
        }
        if (root.left != null) {
            helper(result, root.left, str + "->" + root.left.val);
        }
        if (root.right != null) {
            helper(result, root.right, str + "->" + root.right.val);
        }
    }
}



Method 2: BFS

We use two queue to implement the BFS.

One queue stores the nodes we are traversing.

The other queue stores the path to that node.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Queue<TreeNode> nodes = new LinkedList<>();
        Queue<String> paths = new LinkedList<>();
        nodes.offer(root);
        paths.offer("" + root.val);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.poll();
            String path = paths.poll();
            if (node.left == null && node.right == null) {
                res.add(path);
                continue;
            }
            if (node.left != null) {
                nodes.offer(node.left);
                paths.offer(path + "->" + node.left.val);
            }
            if (node.right != null) {
                nodes.offer(node.right);
                paths.offer(path + "->" + node.right.val);
            }
        }
        return res;
    }
}



Method 3: DFS iterative

Use two stacks.

Implementation is similar to Method 2.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<String> binaryTreePaths(TreeNode root) {
        List<String> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> nodes = new Stack<>();
        Stack<String> paths = new Stack<>();
        nodes.push(root);
        paths.push("" + root.val);
        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            String path = paths.pop();
            if (node.left == null && node.right == null) {
                res.add(path);
                continue;
            }
            if (node.left != null) {
                nodes.push(node.left);
                paths.push(path + "->" + node.left.val);
            }
            if (node.right != null) {
                nodes.push(node.right);
                paths.push(path + "->" + node.right.val);
            }
        }
        return res;
    }
}

Monday, May 8, 2017

4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]

The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5



Solution:

If the total length of two sorted arrays is odd. the median is one number from the array. Otherwise, the median is the average of two numbers from the arrays.

We are actually trying to find the kth smallest number in two sorted arrays.

To find it, we check the (k / 2)-th smallest number (let's say valueA )in array A and (k / 2)-th smallest number (let's say valueB) in array B.

If valueA < valueB, we know we can safely remove all the numbers in array A which are smaller than valueA (including valueA itself). And reduce the problem to find (k - k / 2)-th smallest number in two sorted arrays.

If valueB > valueA, we know we can safely remove all the numbers in array B which are smaller than valueB (including valueB itself).

If we find either the remaining array A or B's length is smaller than k / 2, we know we cannot remove element in it. Thus we remove k / 2 elements from the other array.

The time complexity is O(log(m + n)).



Code:


public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len = nums1.length + nums2.length;
        if (len % 2 == 0) {
            return (findKthElement(nums1, 0, nums2, 0, len / 2) + findKthElement(nums1, 0, nums2, 0, len / 2 + 1)) / 2.0;
        }
        return findKthElement(nums1, 0, nums2, 0, len / 2 + 1);
    }
    
    public int findKthElement(int[] A, int startA, int[] B, int startB, int k) {
        if (startA >= A.length) {
            return B[startB + k - 1];
        }
        if (startB >= B.length) {
            return A[startA + k - 1];
        }
        if (k == 1) {
            return Math.min(A[startA], B[startB]);
        }
        
        int valueInA = startA + k / 2 - 1 < A.length ? A[startA + k / 2 - 1] : Integer.MAX_VALUE;
        int valueInB = startB + k / 2 - 1 < B.length ? B[startB + k / 2 - 1] : Integer.MAX_VALUE;
        
        if (valueInA < valueInB) {
            return findKthElement(A, startA + k / 2, B, startB, k - k / 2);
        }
        return findKthElement(A, startA, B, startB + k / 2, k - k / 2);
    }
}

104. Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.



Solution:

Method 1: recursive

Given any node, if we know the max height of its left child and its right child, we know the max height from this node is the max of his children's max height plus 1.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}



Method 2: iterative

Level order traverse the tree and after each level, increase the count.

Eventually the count is the max height of the tree.



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int level = 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            level++;
        }
        return level;
    }
}

Sunday, May 7, 2017

28. Implement strStr()

Implement strStr().
Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.



Solution:

Method 1: Brute Force

An optimized brute force implementation.

The time complexity is O(n2).



Code:


public class Solution {
    public int strStr(String haystack, String needle) {
        for (int i = 0; i < haystack.length() - needle.length() + 1; i++) {
            int j = 0;
            for (; j < needle.length(); j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == needle.length()) {
                return i;
            }
        }
        return -1;
    }
}



Method 2 : Booye-Moore

The idea is to pre-process a table that when we do the compare of two strings, we know how many steps to skip and continue comparing.

The best time complexity is O(m / n) and worst cast time complexity is O(mn).

The space complexity is O(1).



Code:


public class Solution {
    public int strStr(String haystack, String needle) {
        int m = haystack.length();
        int n = needle.length();
        int[] right = new int[256];
        Arrays.fill(right, -1);
        for (int j = 0; j < n; j++) {
            right[needle.charAt(j)] = j;
        }
        int skip = 0;
        for (int i = 0; i < m - n + 1; i++) {
            skip = 0;
            for (int j = n - 1; j >= 0; j--) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    skip = Math.max(1, right[haystack.charAt(i + j)]);
                    break;
                }
            }
            if (skip == 0) {
                return i;
            }
        }
        return -1;
    }
}

Thursday, May 4, 2017

21. Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.



Solution:

Method 1: iterative

Implementation is straightforward.



Code:


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode dummy = new ListNode(0);
        ListNode curr = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            }
            else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
        if (l1 != null) {
            curr.next = l1;
        }
        else {
            curr.next = l2;
        }
        return dummy.next;
    }
}



Method 2: recursive



Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }
        else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   / \
  9  20
    /  \
   15   7
return its level order traversal as:
[
  [3],
  [9,20],
  [15,7]
]



Solution:

We use a queue to store the nodes in each level.

In every iteration, we need to get the size of queue in order to know how many nodes are in this level (also in the queue).



Code:


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            result.add(list);
        }
        return result;
    }
}

191. Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as the Hamming weight).
For example, the 32-bit integer ’11' has binary representation 00000000000000000000000000001011, so the function should return 3.



Solution:

n & (n - 1) will eliminate a 1 in binary representation.

Therefore we keep doing this until n becomes zero, which means no more 1s in binary representation.



Code:


public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
}

238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Solve it without division and in O(n).
For example, given [1,2,3,4], return [24,12,8,6].
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)



Solution:

We multiply the elements from two directions.

In the first pass, for each element,  we multiply all elements from its left.

In the second pass, for each element, we multiply all elements from its right.

Hence, in any position, the corresponding value is the product of all elements except the element in this position.

The time complexity is O(n) and the space complexity is O(1).



Code:


public class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        int left = 1;
        for (int i = 0; i < n; i++) {
            result[i] = left;
            left *= nums[i];
        }
        int right = 1;
        for (int i = n - 1; i >= 0; i--) {
            result[i] *= right;
            right *= nums[i];
        }
        return result;
    }
}

Wednesday, May 3, 2017

7. Reverse Integer

Reverse digits of an integer.
Example1: x = 123, return 321
Example2: x = -123, return -321
Have you thought about this?
Here are some good questions to ask before coding. Bonus points for you if you have already thought through this!
If the integer's last digit is 0, what should the output be? ie, cases such as 10, 100.
Did you notice that the reversed integer might overflow? Assume the input is a 32-bit integer, then the reverse of 1000000003 overflows. How should you handle such cases?
For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.
Note:
The input is assumed to be a 32-bit signed integer. Your function should return 0 when the reversed integer overflows.



Solution:

Implementation is straightforward. Remember to have boundary check.



Code:


public class Solution {
    public int reverse(int x) {
        
        long res = 0;
        
        while (x != 0) {
            res = res * 10 + x % 10;
            x /= 10;
        }
        
        return res < Integer.MIN_VALUE || res > Integer.MAX_VALUE ? 0 : (int) res;
    }
}

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.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note: 
You may assume k is always valid, 1 ≤ k ≤ array's length.



Solution:

Method 1: find kth smallest

kth largest number in array nums, is the (nums.length - k + 1)th smallest umber in the array.

And its absolute position in an sorted order is nums.length - k.

Therefore, we recursively call 3-way partition until nums[nums.length - k] is finalized.



Code:


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        k = nums.length - k;
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k);
        
        return nums[k];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int lt = lo;
        int gt = hi;
        int i = lo;
        
        while (i <= gt) {
            if (nums[i] < v) {
                exch(nums, lt++, i++);
            }
            else if (nums[i] > v) {
                exch(nums, gt--, i);
            }
            else {
                i++;
            }
        }
        
        if (lt < pos) {
            partition(nums, lt + 1, hi, pos);
        }
        if (lt > pos) {
            partition(nums, lo, lt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}



Method 2: find kth largest

Modify the 3-way partition to put larger number before pivot and smaller number after pivot.

The kth largest number is nums[k - 1] after partition.



Code:


public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return -1;
        }
        
        int lo = 0;
        int hi = nums.length - 1;
        partition(nums, lo, hi, k - 1);
        
        return nums[k - 1];
    }
    
    public void partition(int[] nums, int lo, int hi, int pos) {
        if (hi <= lo) {
            return;
        }
        
        int v = nums[lo];
        int gt = lo;
        int lt = hi;
        int i = lo;
        
        while (i <= lt) {
            if (nums[i] > v) {
                exch(nums, gt++, i++);
            }
            else if (nums[i] < v) {
                exch(nums, lt--, i);
            }
            else {
                i++;
            }
        }
        
        if (gt < pos) {
            partition(nums, gt + 1, hi, pos);
        }
        if (gt > pos) {
            partition(nums, lo, gt - 1, pos);
        }
    }
    
    public void exch(int[] nums, int i, int j) {
        int swap = nums[i];
        nums[i] = nums[j];
        nums[j] = swap;
    }
}