First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.

bucket sort

public class Solution {
    public int firstMissingPositive(int[] A) {
        //Time: O(n)  Space: O(1)
        if (A == null || A.length == 0) {
            return 1;
        }
        
        for (int i = 0; i < A.length; i++) {
            while (A[i] > 0 && A[i] <= A.length && A[i] != i + 1) {
                int temp = A[i];
                //if same, don't need swap
                if (A[temp - 1] == A[i]) {
                    break;
                }
                A[i] = A[temp - 1];
                A[temp - 1] = temp;
            }
        }
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] != i + 1) {
                return i + 1;
            }
        }
        return A.length + 1;
    }
}

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note:
The solution is guaranteed to be unique.

比较直观的是从每个地点开始，但是这题可以只遍历一遍，假设从1开始到4，发现不能走了，说明2，3，4开始也不行。最后检查下，总油量是否大于总消耗。

public class Solution {
    //Time: O(n)  Space: O(1);
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum = 0;
        int cur = 0;
        int index = 0;
        for (int i = 0; i < gas.length; i++) {
            cur += gas[i] - cost[i];
            sum += gas[i] - cost[i];
            if (cur < 0) {
                cur = 0;
                index = i + 1;
            }
        }
        return sum < 0 ? -1 : index;
    }
}

Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

从末尾开始找到第一个降序的地方，记录降序地方小的那个值，继续从末尾开始找到第一个比那个值大的数，两者交换，然后把从末尾到降序的部分反转。

注意有可能整个数组从末尾都是升序的情况。

public class Solution {
    //Time: O(n)  Space: O(1)
    public void nextPermutation(int[] num) {
        if (num == null || num.length == 0) {
            return;
        }
        
        int i = num.length - 1;
        for (; i > 0; i--) {
            if (num[i] > num[i - 1]) {
                break;
            }
        }
        if(i == 0) {
            reverse(num, 0);
            return;
        }
        
        int j = num.length - 1;
        for (; j >= 0; j--) {
            if (num[j] > num[i - 1]) {
                break;
            }
        }
        
        int temp = num[i - 1];
        num[i - 1] = num[j];
        num[j] = temp;
        reverse(num, i);
    }
    
    private void reverse(int[] num, int index) {
        int left = index;
        int right = num.length - 1;
        while (left < right) {
            int temp = num[left];
            num[left] = num[right];
            num[right] = temp;
            left++;
            right--;
        }
    } 
}

Construct Binary Tree from Preorder and Inorder Traversal && Inorder and Postorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

可以利用preorder的第一个肯定是root的性质，同时找到此点在inorder中对应的位置，从而把这两个数组对应分割成左子树和右子树。

update: 在搜索Positions时可以用二分法，这样最坏Time: O(nlogn)

public class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }
    
    private TreeNode build(int[] preorder, int prestart, int preend, 
                           int[] inorder, int instart, int inend) {
        if (preend < prestart || inend < instart) {
            return null;
        }               
        
        TreeNode root = new TreeNode(preorder[prestart]);
        int position = 0;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == preorder[prestart]) {
                position = i;
            }
        }
        
        root.left = build(preorder, prestart + 1, prestart + position - instart,
                          inorder, instart, position - 1);
        root.right = build(preorder, prestart + position - instart + 1, preend,
                           inorder, position + 1, inend);
        return root;
    }
}

Given inorder and postorder traversal of a tree, construct the binary tree.

public class Solution {
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        
        return build(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1);
    }
    
    private TreeNode build(int[] inorder, int instart, int inend,
                           int[] postorder, int poststart, int postend) {
        if (inend < instart || postend < poststart) {
            return null;
        }               
        
        TreeNode root = new TreeNode(postorder[postend]);
        int position = 0;
        for (int i = instart; i <= inend; i++) {
            if (inorder[i] == postorder[postend]) {
                position = i;
            }
        }
        
        root.left = build(inorder, instart, position - 1, 
                          postorder, poststart, poststart + position - instart - 1);
        root.right = build(inorder, position + 1, inend, 
                           postorder, poststart + position - instart, postend - 1);
        return root;
    }
}

2Sum && 3Sum && 3Sum Closest && 4Sum

3Sum Closest

public class Solution {
    //Time: O(n^2)  Space: O(1)
    public int threeSumClosest(int[] num, int target) {
        if (num == null || num.length < 3) {
            return -1;
        }
        
        Arrays.sort(num);
        int closest = Integer.MAX_VALUE / 2;
        for (int i = 0; i < num.length; i++) {
            int left = i + 1;
            int right = num.length - 1;
            while (left < right) {
                int cur = num[i] + num[left] + num[right];
                if (Math.abs(cur - target) < Math.abs(closest - target)) {
                    closest = cur;
                    if (closest == target) {
                        return target;
                    }
                }
                if (cur < target) {
                    left++;
                } else if (cur > target) {
                    right--;
                }
            }
        }
        return closest;
    }
}

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

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

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

就是两次二分找两次边界

public class Solution {
    //Time: O(logn)  Space: O(1)
    public int[] searchRange(int[] A, int target) {
        int[] res = new int[2];
        res[0] = res[1] = -1;
        if (A == null || A.length == 0) {
            return res;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (target <= A[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (A[left] == target) {
            res[0] = left;
        } else if (A[right] == target) {
            res[0] = right;
        }
        
        left = 0;
        right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (target < A[mid]) {
                right = mid;
            } else {
                left = mid;
            }
        }
        if (A[right] == target) {
            res[1] = right;
        } else if (A[left] == target) {
            res[1] = left;
        }
        return res;
    }
}

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

这道题目看了答案，思路比较巧妙。首先把所有的元素都放进HashMap，但是对应的value是0。然后对于每一个元素，先尝试往升序需找，如果HashMap有，就把当前长度+1，同时把HashMap里对应的value设为1。这样下次在遍历到这个值且value为1时，说明这个元素已经被遍历过了，不需要再检测。

public class Solution {
    //Time: O(n)  Space: O(n)
    public int longestConsecutive(int[] num) {
        if (num == null || num.length == 0) {
            return 0;
        }
        
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for (int i : num) {
            map.put(i, 0);
        }
        
        int max = 0;
        for (int i : num) {
            int curmax = 0;
            int temp = i;
            if (map.get(i) == 1) {
                continue;
            }
            
            while (map.containsKey(temp)) {
                curmax++;
                map.put(temp, 1);
                temp++;
            }
            
            temp = i - 1;
            while (map.containsKey(temp)) {
                curmax++;
                map.put(temp, 1);
                temp--;
            }
            max = Math.max(max, curmax);
        }
        return max;
    }
}

Valid Sudoku

Determine if a Sudoku is valid

逐行，逐列，每个小九宫格检查。

public class Solution {
    //Time: O(n^2)  Space: O(n)
    public boolean isValidSudoku(char[][] board) {
        if (board == null || board.length == 0) {
            return false;
        }
        
        for (int i = 0; i < 9; i++) {
            boolean[] map = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    if (!map[board[i][j] - '0']) {
                        map[board[i][j] - '0'] = true;
                    } else {
                        return false;
                    }   
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            boolean[] map = new boolean[10];
            for (int j = 0; j < 9; j++) {
                if (board[j][i] != '.') {
                    if (!map[board[j][i] - '0']) {
                        map[board[j][i] - '0'] = true;
                    } else {
                        return false;
                    }   
                }
            }
        }
        for (int i = 0; i < 9; i += 3) {
            for (int j = 0; j < 9; j += 3) {
                boolean[] map = new boolean[10];
                for (int k = 0; k < 9; k++) {
                    if (board[i + k / 3][j + k % 3] != '.') {
                        if (!map[board[i + k / 3][j + k % 3] - '0']) {
                            map[board[i + k / 3][j + k % 3] - '0'] = true;
                        } else {
                            return false;
                        }
                    }
                }
            } 
        }
        return true;
    }
}

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

左右两个指针往中间遍历，记录对应左右两边的最大值更新，移动最大值小的那一边，这样可以只遍历数组一遍。

public class Solution {
    //Time: O(n)
    public int trap(int[] A) {
        if (A == null || A.length <= 1) {
            return 0;
        }
        
        int left = 0;
        int leftmax = A[left];
        int right = A.length - 1;
        int rightmax = A[right];
        int sum = 0;
        while (left < right) {
            if (rightmax > leftmax) {
                left++;
                sum += leftmax - A[left] > 0 ? leftmax - A[left] : 0;
                leftmax = Math.max(leftmax, A[left]);
            } else {
                right--;
                sum += rightmax - A[right] > 0 ? rightmax - A[right] : 0;
                rightmax = Math.max(rightmax, A[right]);
            }
        }
        return sum;
    }
}

Search in Rotated Sorted Array I & II

Suppose a sorted array 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.

二分法，对于旋转的数组，至少有一半是已经sorted，首先判断那部分是sorted，再判断target在哪部分里。

 public class Solution {  
    //Time: O(logn) Space: O(1)  
    public int search(int[] A, int target) {  
           if (A == null || A.length == 0) {  
                return -1;  
           }  
             
           int start = 0;  
           int end = A.length - 1;  
           while (start + 1 < end) {  
                int mid = start + (end - start) / 2;  
                if (A[mid] == target) {  
                     return mid;  
                }   
                if (A[start] < A[mid]) {  
                     if (A[start] <= target && target < A[mid]) { // left are sorted  
                          end = mid;  
                     } else {  
                          start = mid;  
                     }  
                } else {  
                     if (A[mid] < target && target <= A[end]) { // right are sorted  
                          start = mid;  
                     } else {  
                          end= mid;  
                     }  
                }  
           }  
             
           if (A[start] == target) {  
                return start;  
           } else if (A[end] == target){  
                return end;  
           }  
             
           return -1;  
    }  
} 

Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

public class Solution {
    //Time: O(n) worst case.  Space: O(1)
    public boolean search(int[] A, int target) {
        if (A == null || A.length == 0) {
            return false;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                return true;
            } else if (A[left] < A[mid]) {
                if (A[left] <= target && A[mid] > target) {
                    right = mid;
                } else {
                    left = mid;
                }
            } else if (A[mid] < A[right]) {
                if (A[mid] < target && target <= A[right]) {
                    left = mid;
                } else {
                    right = mid;
                }
            } else {
                if (A[left] == A[mid]) {
                    left++;
                }
                if (A[right] == A[mid]) {
                    right--;
                }
            }
        }
        
        if (A[left] == target || A[right] == target) {
            return true;
        }
        return false;
    }
}

Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

Follow up:

Did you use extra space?
A straight forward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?

对于Space: O(m + n)的方法比较好想。主要是O(1)的解法比较有趣，我们把矩阵第一行和第一列当做mark，来判断当前行和列是否需要置0。在这之前需要两个变量先判断矩阵第一行和第一列是否需要置0。

public class Solution {
    //Time: O(m*n)  Space: O(1)
    public void setZeroes(int[][] matrix) {
        if (matrix == null || matrix.length == 0) {
            return;
        }
        //mark first row and col
        boolean zeroFirstRow = false;
        for (int i = 0; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                zeroFirstRow = true;
                break;
            }
        }
        
        boolean zeroFirstCol = false;
        for (int i = 0; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                zeroFirstCol = true;
                break;
            }
        }
        
        for (int i = 1; i < matrix.length; i++) {
            for (int j = 1; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[i][0] = 0;
                    matrix[0][j] = 0;
                }
            }
        }
        //zero
        for (int i = 1; i < matrix.length; i++) {
            if (matrix[i][0] == 0) {
                zeroRow(matrix, i);
            }
        }
        
        for (int i = 1; i < matrix[0].length; i++) {
            if (matrix[0][i] == 0) {
                zeroCol(matrix, i);
            }
        }
        
        if (zeroFirstRow) {
            zeroRow(matrix, 0);
        }
        if (zeroFirstCol) {
            zeroCol(matrix, 0);
        }
    }
    
    private void zeroRow(int[][] matrix, int row) {
        for (int i = 0; i < matrix[0].length; i++) {
            matrix[row][i] = 0;
        }
    }
    
    private void zeroCol(int[][] matrix, int col) {
        for (int i = 0; i < matrix.length; i++) {
            matrix[i][col] = 0;
        }
    }
}

Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container.

左右两个指针夹逼准则。如果left < right，先记录当前area，left++，反之则right--。因为如果left小的话，如果我们移右指针，结果总比当前area小。

public class Solution {
    //Time: O(n)  Space: O(1)
    public int maxArea(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }
        
        int left = 0;
        int right = height.length - 1;
        int area = 0;
        while (left < right) {
            int h = Math.min(height[left], height[right]);
            area = Math.max(area, h * (right - left));
            if (height[left] == h) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }
}

Plus One

Given a non-negative number represented as an array of digits, plus one to the number.

The digits are stored such that the most significant digit is at the head of the list.

只需要在最后确认下carry是否为1。

public class Solution {
    //Time: O(n)
    public int[] plusOne(int[] digits) {
        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int cur = digits[i] + carry;
            digits[i] = cur % 10;
            carry = cur / 10;
        }
        if (carry == 1) {
            int[] res = new int[digits.length + 1];
            for (int i = 1; i < res.length; i++) {
                res[i] = digits[i - 1];
            }
            res[0] = 1;
            return res;
        }
        return digits;
    }
}

Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

用三个指针，分别对应小于1，等于1，大于1。这道题目的算法我们同样可以应用到quick sort里，处理有重复元素的情况。

public class Solution {
    //Time: O(n)  Space: O(1)
    public void sortColors(int[] A) {
        if (A == null || A.length <= 1) {
            return;
        }
        
        int left = 0;
        int right = A.length - 1;
        int i = 0;
        while (i <= right) {
            if (A[i] == 1) {
                i++;
            } else if (A[i] == 0) {
                int temp = A[i];
                A[i] = A[left];
                A[left] = temp;
                i++;
                left++;
            } else {
                int temp = A[i];
                A[i] = A[right];
                A[right] = temp;
                right--;
            }
        }
    }
}

Pascal's Triangle I & II

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,

Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

利用上一行更新下一行

public class Solution {
    //Time: O(n ^ 2)  Space: O(n ^ 2)
    public ArrayList<ArrayList<Integer>> generate(int numRows) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (numRows <= 0) {
            return res;
        }
        
        ArrayList<Integer> first = new ArrayList<Integer>();
        first.add(1);
        res.add(first);
        for (int i = 1; i < numRows; i++) {
            ArrayList<Integer> last = res.get(res.size() - 1);
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(1);
            for (int j = 0; j < last.size() - 1; j++) {
                tmp.add(last.get(j) + last.get(j + 1));
            }
            tmp.add(1);
            res.add(tmp);
        }
        return res;
    }
}

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

public class Solution {
    //Time: O(n^2) Space: O(n)
    public ArrayList<Integer> getRow(int rowIndex) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if (rowIndex < 0) {
            return res;
        }
        
        res.add(1);
        for (int i = 1; i <= rowIndex; i++) {
            ArrayList<Integer> temp = new ArrayList<Integer>();
            temp.add(1);
            for (int j = 1; j < res.size(); j++) {
                temp.add(res.get(j) + res.get(j - 1));
            }
            temp.add(1);
            res = temp;
        }
        return res;
    }
}

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

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

初始化Index = m + n，从大到小开始merge。

public class Solution {
    //Time: O(m + n)  Space: O(1)
    public void merge(int A[], int m, int B[], int n) {
        int index = m + n;
        while (m > 0 || n > 0) {
            if (m == 0) {
                A[--index] = B[--n];
            } else if (n == 0) {
                return;
            } else {
                if (A[m - 1] > B[n - 1]) {
                    A[--index] = A[--m];
                } else {
                    A[--index] = B[--n];
                }
            }
        }
    }
}

Remove Duplicates from Sorted Array I & II

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

public class Solution {
    //Time: O(n)  Space: O(1)
    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int length = 1;
        for (int i = 1; i < A.length; i++) {
            if (A[i] != A[i - 1]) {
                A[length++] = A[i];
            }
        }
        return length;
    }
}

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

额外用一个变量记录出现次数

public class Solution {
    //Time: O(n)  Space: O(1)
    public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int val = A[0];
        int count = 1;
        int length = 1;
        for (int i = 1; i < A.length; i++) {
            if (A[i] != A[i - 1]) {
                A[length++] = A[i];
                val = A[i];
                count = 1;
            } else {
                if (count == 1) {
                    A[length++] = A[i];
                }
                count++;
            }
        }
        return length;
    }
}

假如需要把所有重复都删除呢?

public int remove(int[] A) {  
      int length = 0;  
      int val = A[0];  
      int count = 1;  
      for (int i = 1; i < A.length; i++) {  
           if (A[i] == val) {  
                count++;  
           } else {  
                if (count == 1) {  
                     A[length++] = val;     
                }  
                count = 1;  
                val = A[i];  
           }  
      }  
      //额外检查最后一个元素  
      if (count == 1) {  
           A[length++] = val;  
      }  
      return length;  
}  

Remove Element

Given an array and a value, remove all instances of that value in place and return the new length.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

public class Solution {
    //Time: O(n)  Space: O(1)
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int length = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != elem) {
                A[length++] = A[i];
            }
        }
        return length;
    }
}

Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

DP，一个变量记录最大值，一个变量记录当前的和

public class Solution {
    //Time: O(n)  Space: O(1)
    public int maxSubArray(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int sum = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < A.length; i++) {
            sum += A[i];
            max = Math.max(max, sum);
            sum = Math.max(0, sum);
        }
        return max;
    }
}

Search Insert Position

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.
[1,3,5,6], 5 → 2
[1,3,5,6], 2 → 1
[1,3,5,6], 7 → 4
[1,3,5,6], 0 → 0

二分搜索法

public class Solution {
    //Time: O(logn)  Space: O(n)
    public int searchInsert(int[] A, int target) {
        if (A == null || A.length == 0) {
            return 0;
        }
        
        int left = 0;
        int right = A.length - 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            if (A[mid] == target) {
                return mid;
            } else if (A[mid] > target) {
                right = mid;
            } else {
                left = mid;
            }
        }
        
        if (A[left] >= target) {
            return left;
        } else if (A[right] >= target) {
            return right;
        } else {
            return right + 1;
        }
    }
}