Merge Two Sorted Lists

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.

Time complexity: O(m+n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ListNode root = null;
        ListNode node = null;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                if (node == null) {
                    node = l1;
                    root = node;
                }
                else {
                    node.next = l1;
                    node = node.next;
                }
                l1 = l1.next;
            }
            else {
                if (node == null) {
                    node = l2;
                    root = node;
                }
                else {
                    node.next = l2;
                    node = node.next;
                }
                l2 = l2.next;
            }
        }
        
        while (l1 != null) {
            if (node == null) {
                node = l1;
                root = node;
            }
            else {
                node.next = l1;
                node = node.next;
            }
            l1 = l1.next;
        }
        
        
        while (l2 != null) {
            if (node == null) {
                node = l2;
                root = node;
            }
            else {
                node.next = l2;
                node = node.next;
            }
            l2 = l2.next;
        }
        return root;
    }
}

Merge Sorted Array

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 to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Idea: Simply do it in reverse order

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] < B[j]) {
                A[k] = B[j];
                --j;
            }
            else {
                A[k] = A[i];
                --i;
            }
            --k;
        }
        
        while (j >= 0) {
            // copy the rest of B into A
            A[k] = B[j];
            --k;
            --j;
        }
    }
};

Merge k Sorted Lists

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Note: Merge sort was used.
Time complexity: O(nlgk).

/** 
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<listnode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (lists.size() == 0) return null;
        ArrayList<listnode> klist = new ArrayList<listnode>();
        for (int i = 0; i &lt; lists.size(); i++) {
            ListNode node = lists.get(i);
            if (node != null) {
                klist.add(node);
            }
        }
        Collections.sort(klist, new Comparator<listnode>() {
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        });
        ListNode root = null;
        ListNode node = null;
        
        while (!klist.isEmpty()) {
            
            if (root == null) {
                root = klist.get(0);
                node = root;
            }
            else {
                node.next = klist.get(0);
                node = node.next;
            }
            
            klist.set(0, klist.get(0).next);
            if (klist.get(0) == null) {
                klist.remove(0);
            }
            
            if (klist.isEmpty()) {
                break;
            }
            
            Collections.sort(klist, new Comparator<listnode>() {
                public int compare(ListNode n1, ListNode n2) {
                    return n1.val - n2.val;
                }
            });
            
            
        }
        return root;
    }
}
 

Search for a Range

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

Key: Binary search

public class Solution {
    public int[] searchRange(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int left = getLeft(A, target);
        int right = getRight(A, target);
        return new int[]{left, right};
    }
    
    public int getLeft(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (end >= start) {
            if (end == start) {
                if (A[start] == target) 
                    return start;
                else 
                    return -1;
            }
            
            int mid = (start + end) / 2;
            if (A[mid] > target) {
                end = mid - 1;
            }
            else if (A[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return -1;
    }
    
    public int getRight(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (end >= start) {
            if (end == start) {
                if (A[start] == target) 
                    return start;
                else 
                    return -1;
            }
            
            int mid = (start + end) / 2;
            if (A[mid] > target) {
                end = mid - 1;
            }
            else if (A[mid] < target) {
                start = mid + 1;
            }
            else {
                if (end - start == 1) {
                    if (A[end] == target) {
                        return end;
                    }
                    else {
                        return start;
                    }
                }
                start = mid;
            }
        }
        return -1;
    }
}

Search a 2D Matrix

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.

Key: Binary search (There may be better code than mine in locating row number. The edge condition is when only two rows left. Incorrect treatment may lead to incorrect answer or infinite loop.)

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        //locate row
        int rs = 0;
        int re = matrix.length - 1;
        while (re - rs > 1) {
            int rm = (rs + re) / 2;
            if (matrix[rm][0] > target) {
                re = rm;
            }
            else if (matrix[rm][0] < target) {
                rs = rm;
            }
            else {
                return true;
            }
        }
        
        int row = 0;
        
        if (matrix[rs][0] > target) {
            return false;
        }
        
        if (matrix[re][0] <= target) {
            row = re;
        }
        else {
            row = rs;
        }
        
        int start = 0;
        int end = matrix[row].length - 1;
        
        if (matrix[row][start] == target || matrix[row][end] == target) {
            return true;
        }
        else if (matrix[row][end] < target) {
            return false;
        }
        else {
            //might be in this row
            while (start < end) {
                if (matrix[row][start] == target || matrix[row][end] == target) {
                    return true;
                }
                int mid = (start + end) / 2;
                if (matrix[row][mid] > target) {
                    end = mid - 1;
                }
                else if (matrix[row][mid] < target) {
                    start = mid + 1;
                }
                else {
                    return true;
                }
            }
            return false;
        }
    }
}

Longest Valid Parentheses

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

public class Solution {
    public int longestValidParentheses(String s) {
        int n = s.countgth();
        int maxCount = 0;
        int lb = 0;
        int count = 0;
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == '('){
                lb++;
                count++;
            }
            if(s.charAt(i) == ')') {
                lb--;
                count++;
            }
            if(lb == 0 && count > maxCount) {
                maxCount = count;
            }
            else if(lb < 0){
                //invalid
                lb = 0;
                count = 0;
            }
        }
        int rb = 0;
        count = 0;
        for(int i = n-1; i >= 0; i--) {
            if(s.charAt(i) == ')'){
                rb++;
                count++;
            }
            if(s.charAt(i) == '(') {
                rb--;
                count++;
            }
            if(lb == 0 && count > maxCount) {
                maxCount = count;
            }
            else if(lb < 0){
                //invalid
                rb = 0;
                count = 0;
            }
        }
        return maxCount;
    }
}

Jump Game II

Jump Game II

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Your goal is to reach the last index in the minimum number of jumps.

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

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

 
Strategy: Greedy (reversed order)

Complexity: O(n^2)

public class Solution {
    public int jump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (A.length == 1) return 0;
        int lastIndex = A.length - 1;
        int steps = 0;
        while (lastIndex > 0) {
            int preIndexMin = lastIndex;
            for (int i=lastIndex - 1; i>=0; i--) {
                if (A[i] >= lastIndex - i) {
                    if (preIndexMin > i) {
                        preIndexMin = i;
                    }
                }
            }
            if (lastIndex == preIndexMin) return -1;
            lastIndex = preIndexMin;
            steps++;
        }
        return steps;
    }
}

Jump Game

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:
A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

Strategy: For each '0' in the array, find if it could be jumped over from its previous indexes, or if we can directly jump to the end.

Complexity: O(n^2)?

public class Solution {
    public boolean canJump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int end = A.length - 1;
        for (int i=0; i<A.length; i++) {
            if (A.length != 1 && A[i] == 0 && i != end) {
                int nextNonZeroIndex = i+1;
                while (nextNonZeroIndex < end) {
                    if (A[nextNonZeroIndex] > 0) {
                        break;
                    }
                    else {
                        nextNonZeroIndex++;
                    }
                }   //max: end
                int j = i - 1;
                boolean continueSearch = false;
                while (j>=0) {
                    if (A[j] >= end - j || A[j] >= nextNonZeroIndex - j) {
                        continueSearch = true;
                        break;
                    }
                    j--;
                }
                if (!continueSearch)
                    return false;
            }
            
        }
        return true;
    }
}

Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

 public static ArrayList spiralOrder(int[][] matrix) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList res = new ArrayList();
        if (matrix.length == 0) {
            return res;
        }
        
        int colStart = 0;
        int colEnd = matrix[0].length - 1;
        int rowStart = 0;
        int rowEnd = matrix.length - 1;
        
        while (colStart <= colEnd && rowStart <= rowEnd) {
            for (int i=colStart; i<=colEnd; i++) {
                res.add(matrix[rowStart][i]);
            }
            rowStart++;
            for (int i=rowStart; i<=rowEnd; i++) {
                res.add(matrix[i][colEnd]);
            }
            colEnd--;
            if (rowStart > rowEnd) break;
            for (int i=colEnd; i>=colStart; i--) {
                res.add(matrix[rowEnd][i]);
            }
            rowEnd--;
            if (colStart > colEnd) break;
            for (int i=rowEnd; i>=rowStart; i--) {
                res.add(matrix[i][colStart]);
            }
            colStart++;
        }
        return res;
    }

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

public class Solution {
    public int[][] generateMatrix(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[][] matrix = new int[n][n];
        int colStart = 0;
        int colEnd = n - 1;
        int rowStart = 0;
        int rowEnd = n - 1;
        int val = 1;
        
        while (colStart <= colEnd && rowStart <= rowEnd) {
            for (int i = colStart; i <= colEnd; i++) {
                matrix[rowStart][i] = val;
                val++;
            }
            
            rowStart++;
            
            for (int i = rowStart; i <= rowEnd; i++) {
                matrix[i][colEnd] = val;
                val++;
            }
            
            colEnd--;
            
            for (int i = colEnd; i >= colStart; i--) {
                matrix[rowEnd][i] = val;
                val++;
            }
            
            rowEnd--;
            
            for (int i = rowEnd; i >= rowStart; i--) {
                matrix[i][colStart] = val;
                val++;
            }
            
            colStart++;
        }
        return matrix;
    }
}

Permutations

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

public class Solution {
 
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
 
        // Start typing your Java solution below
 
        // DO NOT write main() function
 
        ArrayList<ArrayList<Integer>> permutations =
 
               new ArrayList<ArrayList<Integer>>();
 
        permutations.add(new ArrayList<Integer>());
 
        for (int i=0; i<num.length; i++) {
 
            int currentSize = permutations.size();
 
            for (int j=0; j<currentSize; j++) {
 
                ArrayList<Integer> sub = permutations.get(0);
 
                permutations.remove(sub);
 
                for (int k=0; k<=sub.size(); k++) {
 
                    ArrayList<Integer> newSub = new ArrayList<Integer>(sub);
 
                    newSub.add(k,num[i]);
 
                    permutations.add(newSub);
 
                }
 
            }
 
        }
 
        return permutations;
 
    }
 
}