Find Minimum in Rotated Sorted Array | Leetcode

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).

Find the minimum element.

You may assume no duplicate exists in the array.

---

Solution: Use a modified binary search. In each sub-array, if the first number is less than the last number, then this sub-array is sorted, so just return the first number. If this sub-array is not sorted, then break the sub-array into two halves and return the minimum of the minimum numbers from each half.

public class Solution {
    public int findMin(int[] nums) {
        return findMin(nums, 0, nums.length - 1);
    } 
    
    private int findMin(int[] nums, int lo, int hi) {
        if (lo >= hi) return nums[hi];

        // If sub-array is sorted, return the first number.
        boolean isSorted = (nums[lo] < nums[hi]);
        if (isSorted) return nums[lo];

        // If sub-array is not sorted, then need to search in both halves.
        int mid = lo + (hi - lo) / 2;
        return Math.min(findMin(nums, lo, mid), findMin(nums, mid + 1, hi));
    }
}

Maximum Product Subarray | Leetcode

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

For example, given the array [2,3,-2,4],
the contiguous subarray [2,3] has the largest product = 6.

---

Solution: Use 1D dynamic programming, where max[i] is the maximum product ending at i, and min[i] is the minimum product ending at i.

max[i] = max(a[i], (max[i - 1] * a[i]), (min[i - 1] * a[i]))
min[i] = min(a[i], (max[i - 1] * a[i]), (min[i - 1] * a[i]))

We need min[i] because if a[i] is negative, then min[i] * a[i] would produce the biggest product.

public class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0];
        int curMax = max;
        int curMin = max;

        for (int i = 1; i < nums.length; i++) {
            int n = nums[i];

            // We are changing curMax and curMin below,
            // so make sure to use the old value.
            int maxN = curMax * n;
            int minN = curMin * n;

            curMax = Math.max(Math.max(n, maxN), minN);
            curMin = Math.min(Math.min(n, minN), maxN);

            // Using "max = Math.max(max, curMax);"
            // here will exceed the leetcode time limit.
            if (curMax > max) max = curMax;
        }
        
        return max;
    }
}

Reverse Words in a String | Leetcode

Given an input string, reverse the string word by word.

For example,
Given s = "the sky is blue",
return "blue is sky the".

Update (2015-02-12):
For C programmers: Try to solve it in-place in O(1) space.

click to show clarification.

Clarification:

• What constitutes a word?
  A sequence of non-space characters constitutes a word.
• Could the input string contain leading or trailing spaces?
  Yes. However, your reversed string should not contain leading or trailing spaces.
• How about multiple spaces between two words?
  Reduce them to a single space in the reversed string.

---

Solution: Reverse the entire string. Then reverse each word. This means that we should refactor reverseChars() into its own method since we will use it a few times.

Remove all extra spaces. We could have done this when we reverse each word, but the code will be much simpler if we do this step separately.

It is better to do this in-place (update the same character array instead of creating a new array or StringBuilder) as that would require less memory. With a quick search online, I found that most solutions are not in-place and hence arguably are not optimal solutions for this problem.

public class Solution {
    public String reverseWords(String s) {
        if (s.length() == 0) return s;
        
        char[] a = s.toCharArray();
        
        // Reverse the entire string.
        reverseChars(a, 0, a.length - 1);

        // Reverse each word in place.
        int wordStart = -1;
        
        for (int i = 0; i < a.length; i++) {
            if (wordStart >= 0) {
                if (a[i] == ' ') {
                    reverseChars(a, wordStart, i - 1);
                    wordStart = -1;
                }
            } else {
                if (a[i] != ' ') {
                    wordStart = i;
                }
            }
        }

        // Remember to reverse the last word as we will not
        // hit a space at the end of it.
        if (wordStart >= 0) {
            reverseChars(a, wordStart, a.length - 1);
        }
        
        // Trim string and between words.
        int stringIndex = 0;
        boolean hasSpace = false;
        
        for (int i = 0; i < a.length; i++) {
            if (a[i] != ' ') {
                if (hasSpace) {
                    a[stringIndex++] = ' ';
                    hasSpace = false;
                }
                a[stringIndex++] = a[i];
            } else {
                if (stringIndex > 0) {
                    hasSpace = true;
                }
            }
        }
        
        return new String(a, 0, stringIndex);
    }
    
    private static void reverseChars(char[] a, int startInclusive, int endInclusive) {
        for (int i = startInclusive, j = endInclusive; i < j; i++, j--) {
            char c = a[i];
            a[i] = a[j];
            a[j] = c;
        }
    }
}

Evaluate Reverse Polish Notation | Leetcode

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Some examples:

  ["2", "1", "+", "3", "*"] -> ((2 + 1) * 3) -> 9
  ["4", "13", "5", "/", "+"] -> (4 + (13 / 5)) -> 6

---

Solution: Use a stack to hold the numbers and the computation results. Iterate through the tokens from first to last. If you see a number, add it to the stack. If you see an operator, perform it on the top two elements of the stack, and then push the result back into the stack. When done, return the one and only value in the stack as the answer.

public class Solution {
    public int evalRPN(String[] tokens) {
        LinkedList<Integer> stack = new LinkedList<>();
        for (String token: tokens) {
            switch (token) {
                case "+":
                    stack.push(stack.pop() + stack.pop());
                    break;
                case "-":
                    stack.push(-stack.pop() + stack.pop());
                    break;
                case "*":
                    stack.push(stack.pop() * stack.pop());
                    break;
                case "/":
                    int denom = stack.pop();
                    stack.push(stack.pop() / denom);
                    break;
                default:
                    stack.push(Integer.parseInt(token));
            }
        }
        return stack.pop();
    }
}

Max Points on a Line | Leetcode

Given n points on a 2D plane, find the maximum number of points that lie on the same straight line.

---

Solution: For each pair of points (O(N²)), first check whether they are the same point or not. If not, calculate the slope of the line passing through both of them. Keep count of the number of times each slope appears. The number of points on the same line for point X is the total of points which are identical to X (including point X itself) plus the maximum number of points having the same slope with a line passing through X. Since all these lines will pass through X, having the same slope will mean that they are the same line.

Keep track of the maximum count for each point of origin X and return the maximum count among all points as the answer.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    public int maxPoints(Point[] points) {
        if (points.length == 0) return 0;
        
        // At least one point will be on the same line as itself.
        int max = 1;
        
        // Using Double as the key is not ideal for double equality comparison,
        // but it works well enough to pass the Leetcode submission.
        // If we want to use approximate double comparison, we can use a loop
        // in the slope lookup logic to find a matching slope if it exists.
        Map<Double, Integer> slopeCount = new HashMap<>();
        
        for (int i = points.length - 1; i >= 1; i--) {
            int x1 = points[i].x;
            int y1 = points[i].y;
            
            int sameCount = 1; // add points[i] itself
            int verticalCount = 0;
            int horizontalCount = 0;
            int thisSlopeMax = 0;
            
            for (int j = i - 1; j >= 0; j--) {
                int x2 = points[j].x;
                int y2 = points[j].y;
                
                if (x1 == x2 && y1 == y2) {
                    sameCount++;
                } else if (x1 == x2) {
                    verticalCount++;
                } else if (y1 == y2) {
                    // By right not needed, but Java will consider 0.0 != -0.0,
                    // hence it is safer to just avoid this problem altogether.
                    horizontalCount++;
                } else {
                    double slope = ((double) (y1 - y2)) / ((double) (x1 - x2));
                    Integer oldSlopeCount = slopeCount.get(slope);
                    int newSlopeCount = (oldSlopeCount == null) ? 1 : oldSlopeCount + 1;
                    slopeCount.put(slope, newSlopeCount);
                    
                    thisSlopeMax = Math.max(thisSlopeMax, newSlopeCount);
                }
            }
            
            thisSlopeMax = Math.max(thisSlopeMax, Math.max(verticalCount, horizontalCount));
            max = Math.max(max, sameCount + thisSlopeMax);
            
            slopeCount.clear();
        }
        
        return max;
    }
}

Sort List | Leetcode

Sort a linked list in O(n log n) time using constant space complexity.

---

Solution: Probably the only way to do this using constant memory is to use merge sort. We use the technique of finding the middle of the linked list using a slow pointer and a fast pointer. So we can break down a linked lists into two parts, and then sort each part and merge them together.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null) return null;
        if (head.next == null) return head;
        
        // Find the middle of the linked list.
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // Break up the linked list into two parts.
        ListNode first = head;
        ListNode second = slow.next;
        slow.next = null;
        
        // Sort each part separately.
        first = sortList(first);
        second = sortList(second);
        
        // Merge the two linked lists.
        ListNode curr = null;
        while (first != null || second != null) {
            ListNode node;
            if (first == null) {
                node = second;
                second = second.next;
            } else if (second == null) {
                node = first;
                first = first.next;
            } else if (first.val < second.val) {
                node = first;
                first = first.next;
            } else {
                node = second;
                second = second.next;
            }
            if (curr == null) {
                head = curr = node;
            } else {
                curr.next = node;
                curr = node;
            }
        }
        
        return head;
    }
}

Insertion Sort List | Leetcode

Sort a linked list using insertion sort.

---

Solution: For each node in the given linked list, insert it in order into a new linked list. Not easy to get the logic right the first time one writes the code.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null) return null;

        // Start off a new list reusing the same nodes.        
        ListNode newHead = head;
        head = head.next;
        newHead.next = null;
        
        // Insert each node in order.
        while (head != null) {
            // head.next will be overwritten, so save it first.
            ListNode next = head.next;
            newHead = insertInOrder(newHead, head);
            head = next;
        }
        
        return newHead;
    }
    
    private ListNode insertInOrder(ListNode head, ListNode curr) {
        // Find position at which we should insert curr.
        ListNode prev = null;
        ListNode node = head;
        while (node != null && curr.val > node.val) {
            prev = node;
            node = node.next;
        }
        
        // We might need to insert as the head of the list.
        if (prev == null) {
            curr.next = head;
            return curr;
        }
        
        // Insert as per normal inside the list.
        curr.next = prev.next;
        prev.next = curr;
        return head;
    }
}