Daily sign! July 12, Wen

Leetcode41

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public int firstMissingPositive(int[] nums) {
       int i=0;
       while (i<nums.length){
           if (nums[i]==i+1 || nums[i]<=0 || nums[i]>nums.length)   i++;
           else if (nums[i]!=nums[nums[i]-1])   swap(nums,nums[i]-1,i);
           else i++;
       }
       i=0;
       while (i<nums.length && nums[i]==i+1){
           i++;
       }
       return ++i;       
    }
    private void swap(int[] nums, int i, int j)
    {
        int tmp;
        tmp=nums[i];
        nums[i]=nums[j];
        nums[j]=tmp;
    }
}

Daily Sign! July 11, 2017

Leetcode126
This is not my solution. Thanks to the author.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Solution {
    public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
        long[] lengths = {length(p1, p2), length(p2, p3), length(p3, p4),
                length(p4, p1), length(p1, p3),length(p2, p4)}; // all 6 sides
 
        long max = 0, nonMax = 0;
        for(long len : lengths) {
            max = Math.max(max, len);
        }
        int count = 0;
        for(int i = 0; i < lengths.length; i++) {
            if(lengths[i] == max) count++;
            else nonMax = lengths[i]; // non diagonal side.
        }
        if(count != 2) return false; // diagonals lenghts have to be same.
 
        for(long len : lengths) {
            if(len != max && len != nonMax) return false; // sides have to be same length
        }
        return true;
    }
 
    private long length(int[] p1, int[] p2) {
        return (long)Math.pow(p1[0]-p2[0],2) + (long)Math.pow(p1[1]-p2[1], 2);
    }
}

Leetcode126

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
public class Solution {
    public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> res = new ArrayList<>();
        if (beginWord == null || endWord == null || wordList == null) return res;
 
        Set<String> dict = new HashSet<>();
        for (String word : wordList) {
            dict.add(word);
        }
 
        if (!dict.contains(endWord)) {
            return res;
        }
 
        Set<String> set1 = new HashSet<>();
        Set<String> set2 = new HashSet<>();
        set1.add(beginWord);
        set2.add(endWord);
 
        Map<String, Set<String>> map = new HashMap<>(); // store paths
        bfs(dict, set1, set2, map, true);
 
        List<String> temp = new ArrayList<>();
        temp.add(beginWord);
 
        dfs(map, res, temp, beginWord, endWord);
        return res;
    }
 
    private void dfs(Map<String, Set<String>> map, List<List<String>> res, List<String> temp, String currWord, String endWord) {
        if (currWord.equals(endWord)) {
            res.add(new ArrayList<>(temp));
        } else {
            if (map.containsKey(currWord)) {
                for (String next : map.get(currWord)) {
                    temp.add(next);
                    dfs(map, res, temp, next, endWord);
                    temp.remove(temp.size() - 1);
                }
            }
        }
    }
 
    private void bfs(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, Set<String>> map, boolean forward) {
        if (set1.size() > set2.size()) {
            bfs(dict, set2, set1, map, !forward);
            return;
        }
 
        dict.removeAll(set1);
 
        Set<String> nextLevelSet = new HashSet<>();
        boolean connected = false;
        for (String str : set1) {
            char[] chs = str.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                char oldChar = chs[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    chs[i] = c;
                    String newStr = new String(chs);
 
                    if (dict.contains(newStr) || set2.contains(newStr)) {
                        if (!connected) { // the checking is a small optimization
                            if (set2.contains(newStr)) {
                                connected = true;
                            } else {
                                nextLevelSet.add(newStr);
                            }
                        }
 
                        String key = forward ? str : newStr;
                        String val = forward ? newStr : str;
 
                        if (!map.containsKey(key)) {
                            map.put(key, new HashSet<>());
                        }
 
                        map.get(key).add(val);
                    }
                }
                chs[i] = oldChar;
            }
        }
 
        if (!connected && !nextLevelSet.isEmpty()) {
            bfs(dict, nextLevelSet, set2, map, forward);
        }
    }
}

PriorityQueue Example

Leetcode373
This is a problem to pick up largest/least k numbers from array. A good method is to use min-heap or max-heap, in java, PriorityQueue.

First Method
We define an member inner class and implement comparable interface, which is clear and recommended!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.List;
public class S1 {
    /*  
        define a class -- tuple
        implements an interface comparable
        Comparable provides a function compareTo()
        If not override, it follows the natural order defined in Java
    */
    class Tuple implements Comparable<Tuple> {
        int x, y, val;
        public Tuple (int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
 
        @Override
        public int compareTo (Tuple that) {
            return this.val - that.val;
        }
    }
 
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<Tuple> pq = new PriorityQueue<Tuple>();
        int m = nums1.length;
        int n = nums2.length;
        List<int[]> res = new LinkedList<int[]>();
 
        if(nums1.length == 0 || nums2.length == 0 || k <= 0) 
            return res;
 
        for(int j = 0; j <= n-1; j++) 
            pq.offer(new Tuple(0, j, nums1[0]+nums2[j]));
 
        for(int i = 0; i < Math.min(k, m *n); i++) {
            Tuple t = pq.poll();
            // extract the current min value tuple
            res.add(new int[]{nums1[t.x], nums2[t.y]});
            if(t.x == m - 1) continue;
           /*            
            * always we put the right neighbour into heap because
            * X A B
            * * ?
            * .
            * we have knwo X, A, the next least can be ? or B. In fact, ? is not
            * possible for * < ? 
            * so the possible can be * or B
            */
            pq.offer(new Tuple (t.x + 1, t.y, nums1[t.x + 1] + nums2[t.y]));
        }
        return res;
    }
}

Second Method
The most basic and prevalent method and rewrite the compare method to determine it is min heap or max heap.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.List;
 
public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        LinkedList<int[]> list = new LinkedList<>();
        if (nums1.length == 0 || nums2.length == 0) return list;
 
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            new Comparator<int[]>() {
 
                @Override
                public int compare(int[] l1, int[] l2) {
                    return nums1[l1[0]]-nums1[l2[0]]+ nums2[l1[1]]- nums2[l2[1]];
                }
            }
        );
        // PriorityQueue(Comparator<? super E> comparator)
        /* Creates a PriorityQueue with the default initial 
        capacity(11) and whose elements are ordered according 
        to the specified comparator.*/
 
        for (int i = 0; i < nums1.length; i++) {
            pq.offer(new int[]{i, 0});
        }
 
        for(int i = 0; i < Math.min(k, nums1.length * nums2.length ); i++) {
            int[] min = pq.poll();
            list.add(new int[]{nums1[min[0]], nums2[min[1]]});
            if (min[1] == nums2.length-1) 
                continue;
            pq.offer(new int[]{min[0], min[1]+1});
        }
        return list;
    }
}

Third Method
Here, we use lambda expression and simplify the code.
It is highly recommended to read this tutorial! Also looking forward Java 9 with more flexible functional programming!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public List<int[]> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->nums1[a[0]]+nums2[a[1]]-nums1[b[0]]-nums2[b[1]]);
        List<int[]> res = new LinkedList<>();
 
        if(nums1.length==0 || nums2.length==0 || k==0) return res;
 
        for(int i=0; i<nums1.length; i++) 
            pq.offer(new int[]{i, 0});
 
        for(int i = 0; i < Math.min(k, nums1.length * nums2.length); i++){
            int[] min = pq.poll();
            res.add(new int[]{nums1[min[0]], nums2[min[1]]});
            if(min[1] == nums2.length-1) 
                continue;
            pq.offer(new int[]{min[0], min[1]+1});
        }
        return res;
    }
}

Daily sign! July 10, Mon

Leetcode554
Here is a good introduction to traversal of HashMap and TreeMap!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int leastBricks(List<List<Integer>> wall) {
        Map<Integer, Integer> map = new HashMap<>();
        int max = 0;
        for(List<Integer> list : wall){
            int count = 0;
            for(int i = 0; i<list.size() -1; i++){
                count += list.get(i);
                int temp = map.getOrDefault(count, 0) +1;
                map.put(count, temp);
                max = Math.max(max, temp);    
            }
        }
        return wall.size() - max;        
    }
}

Daily sign! July 9, Sun

Leetcode365
This solution requires number theory knowledge base. If you don’t know anything about it, never mind!
Leetcode198

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * DP solution O(n) space
 */
public class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        int rob = 0;
        int notrob = 0;
 
        for(int num : nums){
            int temprob = rob;
            rob = notrob + num;
            notrob = Math.max(notrob, temprob);
        }
        return Math.max(rob, notrob);
    }
}

Leetcode213

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int rob(int[] nums) {
        if(nums.length == 0) return 0;
        int robFirst = nums[0];
        int notRobFirst = nums[0];
 
        int rob = 0; 
        int notrob = 0;
        for(int i =1; i<nums.length; i++){
            if(i != 1 && i != nums.length -1){
                int temp = robFirst;
                robFirst = notRobFirst + nums[i];
                notRobFirst = Math.max(temp, notRobFirst);
            }
            int temprob = rob;
            rob = notrob + nums[i];
            notrob = Math.max(temprob, notrob);
        }
 
        return Math.max(Math.max(rob, notrob), Math.max(robFirst, notRobFirst));
 
    }
}

Leetcode337
Yeah, it is interesting! I never imagined about DFS + DP, although the refer saids it is greedy, which i don’t agree with.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Its time complexity is O(n), space complexity is also O(n)
 *
 */
public int rob(TreeNode root) {
    int[] res = robSub(root);
    return Math.max(res[0], res[1]);
}
 
private int[] robSub(TreeNode root) {
    if (root == null) return new int[2];
 
    int[] left = robSub(root.left);
    int[] right = robSub(root.right);
    int[] res = new int[2];
 
    res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
    res[1] = root.val + left[0] + right[0];
 
    return res;
}

Now I post a naive solution and could you analyze it time complexity?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int rob(TreeNode root) {
         return helper(root, false);
    }
 
    public int helper(TreeNode root, boolean ifrob){
        if(root == null) return 0;
        if(ifrob){
            // the last level is robed
            return  helper(root.left, false) + helper(root.right, false);
        }else{
            //the last level is not rob
            return Math.max(helper(root.left, false) + helper(root.right, false), root.val + helper(root.left, true) + helper(root.right, true));
        }
    }
}

Now we analyze it its complexity from the visited times of every node.

Root node: O(1)
Level 1: 2 * O(1)
level 2: 2 * 2 * O(1)
.......
level lg(n): 2^lg(n) * O(1);
Time complxity = 2^0 * 2^0 + 2^1 * 2^1 + ... + 2^logn * 2^logn = 2^0 + 2^2 + 2^4 + ... + 2^2x| x =logn 
Based on geometric progression,
we can get time complexity is O(4log(n)) = O(n2)
WORST_CASE
The tree is a singly linked list:
Root 1:
level 1: 2
level 2: 4
.......
level n: 2^n
Time complexity = 2^(n+1) = O(a^n) SCARY ALGORITHM!

Leetcode55

1
2
3
4
5
6
7
8
9
10
public class Solution {
    public boolean canJump(int[] nums) {
        int reachable = 0;
        for (int i=0; i<nums.length; ++i) {
            if (i > reachable) return false;
            reachable = Math.max(reachable, i + nums[i]);
        }
        return true;
    }
}

Leetcode567

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public boolean checkInclusion(String s1, String s2) {
        int len1 = s1.length(), len2 = s2.length();
        if (len1 > len2) return false;
 
        int[] count = new int[26];
        for (int i = 0; i < len1; i++) {
            count[s1.charAt(i) - 'a']++;
            count[s2.charAt(i) - 'a']--;
        }
        if (allZero(count)) return true;
 
        for (int i = len1; i < len2; i++) {
            count[s2.charAt(i) - 'a']--;
            count[s2.charAt(i - len1) - 'a']++;
            if (allZero(count)) return true;
        }
 
        return false;
    }
 
    private boolean allZero(int[] count) {
        for (int i = 0; i < 26; i++) {
            if (count[i] != 0) return false;
        }
        return true;
    }
}

Daily sign! July 8, Sat

Leetcode28
String.length() is a O(1) operation, for string class has the field length.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int strStr(String haystack, String needle) {
        if(needle.length() == 0) return 0;
        for(int i =0; i <= haystack.length() -needle.length(); i++){
            int t =i;
            for(int j=0; j<needle.length() ;j++){
                if(haystack.charAt(t) == needle.charAt(j)){
                    t++;
                }else{
                    break;
                }
            }
            if(t >= i+ needle.length()) return i;
        }
        return -1;
    }
}

Leetcode162
This problem is easy and you are only required to find the non-monotone increasing location.

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int findPeakElement(int[] nums) {
        for(int i =1; i<nums.length;i++){
            if(nums[i] > nums[i-1]){
                continue;
            }else{
                return i-1;
            }
        }
        return nums.length -1;
    }
}

Leetcode124
This problem is hard but the idea and implementation are simple.
You can think about Path Sum, which walk through an array and get max sum of subarray. We use a global to store max value of current subtree. ALSO helper function return the the max subroutine of subtree. In this way, we can have two kinds of values, where one is max sum in in the subtree while the other one is max sun use the subtree.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
    private int max = 0;
    public int maxPathSum(TreeNode root) {
        if(root == null) return 0;
        max =root.val;
        helper(root);
        return max;
 
    }
 
    public int helper(TreeNode root){
        if(root == null) return 0;
        int left = helper(root.left);
        int right = helper(root.right);
        int temp = root.val + (left>0?left:0) + (right>0?right:0);
        max = Math.max(max, temp);
        return root.val + Math.max(0, Math.max(left, right));
    }
}

Leetcode300
This solution of O(nlgn) is really subtle!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        int len = 0;
        for (int num : nums) {
            int i = Arrays.binarySearch(dp, 0, len, num);
            if (i < 0) {
                i = -(i + 1);
            }
            dp[i] = num;
            if (i == len) {
                len++;
            }
        }
        return len;
    }
}

Leetcode125

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public class Solution {
    public boolean isPalindrome(String s) {
        if(s == null || s.length() <= 1) return true;
        int start = 0;
        int end = s.length() -1;
 
        while(end >= start){
            char charStart = s.charAt(start);
            if(!( charStart >= 'a' && charStart <= 'z' || charStart >= 'A' && charStart <= 'Z'  || charStart >= '0' && charStart <= '9')){
                start ++;
                continue;
            }
            char charEnd = s.charAt(end);
            if(!( charEnd >= 'a' && charEnd <= 'z' || charEnd >= 'A' && charEnd <= 'Z' || charEnd >= '0' && charEnd <= '9')){
                end --;
                continue;
            }
            if(!(charEnd == charStart || (charEnd - charStart) == 'a' -'A' && charStart >= 'A'||  (charEnd - charStart) == 'A' -'a' && charEnd >='A')) {
                return false;
            }
            start ++;
            end --;
 
        }
 
        return true;
    }
}

Leetcode56
To be honest, this is a brute-force method, which require us to traverse the list from back to front. It is a O(n2) method, which beats 99%. What unbalanced test case!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        for(int i = intervals.size() -1; i>=0; i--){
            int j = i+1;
            while(j<intervals.size()){
                Interval i1 = intervals.get(i);
                Interval i2 = intervals.get(j);
                if(i1.start <= i2.start){
                    if(i2.start <= i1.end){
                        if(i2.end >= i1.end){
                            i1.end = i2.end;
                        }
                        intervals.remove(j);
                    }else{
                        j++;
                    }
                }else{
                    if(i1.start <= i2.end){
                        if(i1.end <= i2.end){
                            i1.start = i2.start;
                            i1.end = i2.end;
                        }else{
                            i1.start = i2.start;
                        }
                        intervals.remove(j);
                    }else{
                        j++;
                    }   
                }
            }
        }
        return intervals;
    }
}

Leetcode112
This problem is disgusting! LEAF cannot be NULL, so the path can not be ended with null.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * // Elegant write-up
 * public class Solution {
 *    public boolean hasPathSum(TreeNode root, int sum) {
 *        if(root == null) return false;
 *        if(root.left == null && root.right == null) return sum == root.val;
 *        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum -     
 * root.val);
 *    }
 *}
 */
public class Solution {
    public boolean hasPathSum(TreeNode root, int sum) {
        if(root == null) return false;
        return  helper(root, sum);
    }
 
    public boolean helper(TreeNode root, int sum){
        if(root.left  == null && root.right == null){
            return sum == root.val;
        }
        boolean res = false;
        if(root.left  != null)
            res = res || helper(root.left, sum - root.val);
        if(root.right != null)
            res = res|| helper(root.right, sum - root.val);
        return res;
    }
}

Leetcode114

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return;
        helper(root);
    }
    public TreeNode helper(TreeNode root){
        if(root.left == null && root.right == null){
            return root;
        }
        TreeNode left = root.left == null?null:helper(root.left);
        TreeNode right = root.right == null?null:helper(root.right);
        root.right = left;
        root.left = null;
        TreeNode node = root;
        while(node.right != null){
            node =node.right;
        }
        node.right = right;
 
        return root;
    }
}

Leetcode591
I have NEVER seen such disgusting problem! It is troublesome, boring and exhausting. If you are not a over-energetic young man, keep away from it!

Error fixed! WordPress?

It is really interesting. Bing wrongly redirect my path to a Japan shopping website and I cannot login my dashboard. I check my database in serve which displays everything is Ok. All right, I reset my password and get in successfully. Some days later, I cannot login my blogs and the error of debugging tells me index.html cannot require wp-blog-header.php. In fact, there is no such file in my server. Fetch it from WP-Git and upload. It may help you fix such error.

Daily Sing–Sat, July 1

Leetcode236

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
		/**
        LinkedList<TreeNode> list1 = new LinkedList<>();
        LinkedList<TreeNode> list2 = new LinkedList<>();
        track(root, p, list1);
        track(root, q, list2);
        TreeNode res = new TreeNode(-1);
        for(int i =0; i<list1.size() && i <list2.size(); i++){
            if( list1.get(i) == list2.get(i)){
                res = list1.get(i);
            }else{
                break;
            }
        }
 
        return res;
        */
 
        if(root == p || root == q){
            return root;
        }else if(root == null){
            return null;
        }
 
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
 
        if(left == null && right == null){
            return null;
        }else if(left != null && right != null){
            return root;
        }else{
            return left!=null?left:right;
        }
 
    }
 
    public boolean track(TreeNode root, TreeNode p, LinkedList<TreeNode> list){
        if(root == null){
            return false;
        }
        if(root == p){
            list.addFirst(root);
            return true;       
        }else{
            if(track(root.left, p, list) || track(root.right, p, list)){
                list.addFirst(root);
                return true;
            }
        }
        return false;
    }
}>/pre>
<a href="https://leetcode.com/problems/rotate-image/#/description">Leetcode48</a> Another in-algorithm can found <a href="https://discuss.leetcode.com/topic/6796/a-common-method-to-rotate-the-image">here</a>!
<pre lang="java" line="1">.
public class Solution {
    public void rotate(int[][] matrix) {
        int[][] m1 = new int[matrix.length][matrix[0].length];
 
        for(int i=0; i< matrix.length; i++){
            for(int j =0; j<matrix[0].length; j++){
                m1[j][matrix.length-1-i] = matrix[i][j];
            }
        }
        for(int i=0; i< matrix.length; i++){
            for(int j =0; j<matrix[0].length; j++){
                matrix[i][j] = m1[i][j];
            }
        }
    }
}

public class Solution {
public int missingNumber(int[] nums) {
if(nums.length == 0 || nums == null) return 0;
Arrays.sort(nums);

int low = 0;
int high = nums.length -1;

while(low