Leetcode: Search in Rotated Sorted Array & Search in Rotated Sorted Array II

Search in Rotated Sorted Array

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.

Analysis:

This image is from http://fisherlei.blogspot.com/2013/01/leetcode-search-in-rotated-sorted-array.html

public class Solution {
    public int search(int[] A, int target) {
        int l = 0;
        int r = A.length - 1;
        while (l <= r) {
            int m = (l + r) / 2;
            if (A[m] == target) {
                return m;
            }
            if (A[m] >= A[l]) {
                if (A[l] <= target && target < A[m]) {
                    r = m - 1;
                } else {
                    l = m + 1;
                }
            } else {
                if (A[m] < target && target <= A[r]) {
                    l = m + 1;
                } else {
                    r = m - 1;
                }
            }
        }
        return -1;
    }
}

Note:

sdfsdfweerwr

Search in Rotated Sorted Array II

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.

 

 

Reference

FacebookTwitterGoogle+Share

Leetcode: Best Time to Buy and Sell Stock

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.

Solution: One Pass O(n) time.

For each day i,

1. think of if sell it at day i, compare the profit with maxProfit.

2. check if day i is a better day than any previous day to buy a stock, meaning the price is cheaper than any previous day, then we buy the stock at day i.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length <= 1) {
        return 0;
    }
    int maxProfit = 0;
    int sum = 0;
    int buyDate = 0;
    for (int i = 1; i < prices.length; i++) {
        maxProfit = Math.max(maxProfit, prices[i] - prices[buyDate]);
        if (prices[i] < prices[buyDate]) {
            buyDate = i;
        }
    }
    return maxProfit;
}

 

Leetcode: Search a 2D Matrix

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 from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        int start = 0;
        int end = m * n - 1;
        while (start <= end) {
            int mid = (start + end) / 2;
            int midVal = matrix[mid / n][mid % n];
            if (midVal == target) {
                return true;
            } else if (midVal > target) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}

Note: O(log(m*n))

Leetcode: Binary Tree Level Order Traversal II

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

For example:
Given binary tree {3,9,20,#,#,15,7},

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

public class Solution {
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> result = new LinkedList<List<Integer>>();
        if (root == null) {
            return result;
        }
        List<TreeNode> currLevel = new LinkedList<TreeNode>();
        currLevel.add(root);
        while (currLevel.size() > 0) {
            result.add(0, new LinkedList<Integer>());
            List<TreeNode> nextLevel = new LinkedList<TreeNode>();
            while (currLevel.size() > 0) {
                TreeNode runner = currLevel.remove(0);
                result.get(0).add(runner.val);
                if (runner.left != null) {
                    nextLevel.add(runner.left);
                }
                if (runner.right != null) {
                    nextLevel.add(runner.right);
                }
            }
            currLevel = nextLevel;
        }
        return result;
    }
}

Leetcode: 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.

    public int maxArea(int[] height) {
        int maxArea = 0;
        int left = 0;
        int right = height.length - 1;
        while (left < right) {
            maxArea = Math.max(maxArea, calculateArea(height, left, right));
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return maxArea;
    }

    public int calculateArea(int[] height, int left, int right) {
        return Math.abs(right - left) * Math.min(height[left], height[right]);
    }

Note:

For any container, its volume depends on the shortest board.

Two-pointer scan. And always move with shorter board index.

Leetcode: Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Follow up:
Could you do this in-place?

public class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        if (n <= 1 || matrix.length <= 1 || n != matrix.length) {
            return;
        }
        int mid = (n - 1) / 2;
        int offset = 0;
        while (offset <= mid) {
            for (int i = offset; i < n - 1 - offset; i++) {
                int tmp = matrix[offset][i];
                matrix[offset][i] = matrix[n - 1 - i][offset];
                matrix[n - 1 - i][offset] = matrix[n - 1 - offset][n - 1 - i];
                matrix[n - 1 - offset][n - 1 - i] = matrix[i][n - 1 - offset];
                matrix[i][n - 1 - offset] = tmp;
            }
            offset++;
        }

    }
}

Leetcode: Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

public class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<String>();
        if(n>0){
            generateParenthesis("", n, n, result);
        }
        return result;
    }
   
    public void generateParenthesis(String prefix, int left, int right, List<String> result){
        if(left>right){
            return;
        }
        if(left==0){
             for(int i=0;i<right;i++){
                 prefix+=")";
             }
             result.add(prefix);
             return;
        }
        if(left<right){
            generateParenthesis(prefix+")", left, right-1, result);
        }
        generateParenthesis(prefix+"(", left-1, right, result);    
    }
}

Note: The key point of this problem is when generating parentheses, the number of left parentheses being used so far is always larger than the number of right parentheses. In the algorithm. left and right means # of parentheses not being used so far.