LeetCode 51. N-Queens

Problem:

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens’ placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

Solution:

Backtracking.

public class Solution {
    char[][] grid;
    int n;
    List<List<String>> solutions = new ArrayList<List<String>>();
    
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        grid = new char[n][n];
        solve(0);
        return solutions;
    }
    
    private void solve(int row) {
        List<Integer> opts = nextStep(row);
        if (opts.size() == 0) {
            return;
        }
        for (int j: opts) {
            grid[row][j] = 'Q';
            if (row == n - 1) {
                List<String> sol = new ArrayList<String>();
                for (int i = 0; i < n; i++) {
                    String r = "";
                    for (int k = 0; k < n; k++) {
                        if (grid[i][k] == 'Q') r += "Q";
                        else r += ".";
                    }
                    sol.add(r);
                }
                solutions.add(sol);
            }
            else {
                solve(row + 1);
            }
            grid[row][j] = '.';
        }
    }
    
    private List<Integer> nextStep(int row) {
        List<Integer> opts = new ArrayList<Integer>();
        for (int j = 0; j < n; j++) {
            boolean opt = true;
            for (int i = 0; i < row; i++) {
                if (grid[i][j] == 'Q') {
                    opt = false;
                    break;
                }
            }
            int l = j, r = j;
            for (int i = row - 1; i >= 0; i--) {
                l--; r++;
                if (l >= 0 && grid[i][l] == 'Q') {
                    opt = false;
                    break;
                }
                if (r < n && grid[i][r] == 'Q') {
                    opt = false;
                    break;
                }
            }
            if (opt) opts.add(j);
        }
        return opts;
    }
}

LeetCode 160. Intersection of Two Linked Lists

Problem:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

  • If the two linked lists have no intersection at all, return null.
  • The linked lists must retain their original structure after the function returns.
  • You may assume there are no cycles anywhere in the entire linked structure.
  • Your code should preferably run in O(n) time and use only O(1) memory.

Solution:

First find the lengths of two linked lists.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) return null;
        int la = 0, lb = 0;
        ListNode curA = headA, curB = headB;
        while (curA != null) {
            la++;
            curA = curA.next;
        }
        while (curB != null) {
            lb++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        for (int i = 0; i < Math.abs(la - lb); i++) {
            if (la < lb) curB = curB.next;
            else curA = curA.next;
        }
        while (curA != curB) {
            curA = curA.next;
            curB = curB.next;
        }
        return curA;
    }
}

LeetCode 128. Longest Consecutive Sequence

Problem:

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.

Solution:

I’m so dumb. I used union find but it could be just O(n) as shown below. 🙁

public class Solution {
    HashMap<Integer, Integer> reference = new HashMap<Integer, Integer>();
    HashMap<Integer, Integer> length = new HashMap<Integer, Integer>();
    HashMap<Integer, Boolean> in = new HashMap<Integer, Boolean>();
    public int longestConsecutive(int[] nums) {
        for (int num: nums) {
            reference.put(num, num);
        }
        for (int num: nums) {
            if (reference.containsKey(num + 1)) {
                union(num, num + 1);
            }
            if (reference.containsKey(num - 1))
                union(num - 1, num);
        }
        for (int num: nums) {
            find(num);
        }
        for (int num: nums) {
            if (in.containsKey(num)) continue;
            int id = reference.get(num);
            if (!length.containsKey(id))
                length.put(id, 1);
            else 
                length.put(id, length.get(id) + 1);
            in.put(num, true);
        }
        int max = 0;
        for (int v: length.values()) {
            if (v > max) max = v;
        }
        return max;
    }
    
    private void union(int a, int b) {
        int roota = find(a);
        int rootb = find(b);
        if (roota == rootb) return;
        reference.put(a, b);
    }
    
    private int find(int p) {
        int root = p;
        while (root != reference.get(root)) {
            root = reference.get(root);
        }
        while (p != root) {
            int newp = reference.get(p);
            reference.put(p, root);
            p = newp;
        }
        return root;
    }
}

Solution from Sayings, O(n)

public class Solution {
public int longestConsecutive(int[] nums) {

    Set<Integer> set = new HashSet<Integer>();

    for(int n: nums) set.add(n);

    int max = 0;

    for(int n: nums){
        int count = 0;
        if(set.isEmpty()) break;

        int val = n;
        while(set.remove(val--))
            count ++;

        val = n;
        while(set.remove(++val))
            count ++;

        max = Math.max(count,max);
    }

    return max;

    }
}

LeetCode 220. Contains Duplicate III

Problem:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Solution:

BST complexity O(n log k). Solution from justcodeit

public static boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
        if (nums.length <= 0 || k <= 0) {
            return false;
        }
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < nums.length; i++) {
            int val = nums[i];
            /*
             * Returns the greatest element in this set less than or equal to
             * the given element, or null if there is no such element. Specified
             * by: floor(...) in NavigableSet Parameters: e the value to match
             * Returns: the greatest element less than or equal to e, or null if
             * there is no such element
             */
            if (set.floor(val) != null && (set.floor(val) + t) >= val)
                return true;
            /*
             * Returns the least element in this set greater than or equal to
             * the given element, or null if there is no such element. Specified
             * by: ceiling(...) in NavigableSet Parameters: e the value to match
             * Returns: the least element greater than or equal to e, or null if
             * there is no such element
             */
            if (set.ceiling(val) != null && (set.ceiling(val) - t) <= val)
                return true;
            set.add(val);
            if (i >= k)
                set.remove(nums[i - k]);
        }
        return false;
    }

LeetCode 219. Contains Duplicate II

Problem:

Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.

Solution:

HashTable

public class Solution {
    Map<Integer, Integer> values = new HashMap<Integer, Integer>();
    public boolean containsNearbyDuplicate(int[] nums, int k) {
        for (int i = 0; i < nums.length; i++) {
            int value = nums[i];
            if (values.get(value) != null) {
                int previous = values.get(value);
                if (Math.abs(previous - i) <= k) return true;
            }
            values.put(value, i);
        }
        return false;
    }
}

LeetCode 217. Contains Duplicate

Problem:

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

Solution:

public class Solution {
    public boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        for (int i = 0; i < nums.length; i++) {
            set.add(nums[i]);
            if (set.size() != i + 1) return true;
        }
        return false;
    }
}

LeetCode 199. Binary Tree Right Side View

Problem:

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

For example:
Given the following binary tree,

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

You should return [1, 3, 4].

Credits:
Special thanks to @amrsaqr for adding this problem and creating all test cases.

Solution:

visited takes care of whether a certain level already has the rightmost node in the arraylist. Can also be done with iterative BFS.

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    Set<Integer> visited = new HashSet<Integer>();
    List<Integer> result = new ArrayList<Integer>();
    public List<Integer> rightSideView(TreeNode root) {
        visit(root, 0);
        return result;
    }
    
    private void visit(TreeNode root, int level) {
        if (root == null) return;
        if (!visited.contains(level)) {
            visited.add(level);
            result.add(root.val);
        }
        visit(root.right, level+1);
        visit(root.left, level+1);
    }
}

LeetCode 316. Remove Duplicate Letters

Problem:

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution:

Two cases, letter already in stringbuilder and not. If in, only need to compare the one after the earlier position with the letter; if not, reduce from the last character and put the new letter at a proper position.

Why am I so dumb now this took me sooo long 😭

public class Solution {
    StringBuilder t = new StringBuilder();
    boolean[] onStack = new boolean[26];
    int[] num = new int[26];
    int[] pos = new int[26];
    public String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            num[chars[i] - 'a']++;
        }
        
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            num[c - 'a']--;
            if (!onStack[c - 'a']) {
                int index = t.length() - 1;
                while (index >= 0 && t.charAt(index) > c && num[t.charAt(index) - 'a'] > 0) {
                    onStack[t.charAt(index) - 'a'] = false;
                    t.deleteCharAt(index);
                    index--;
                }
                pos[c - 'a'] = t.length();
                onStack[c - 'a'] = true;
                t.append(c);
            }
            else {
                int index = pos[c - 'a'] + 1;
                if (index >= t.length()) continue;
                if (t.charAt(index) < c) {
                    t.deleteCharAt(pos[c - 'a']);
                    pos[c - 'a'] = t.length();
                    t.append(c);
                }
            }
            //System.out.println(t.toString());
        }
        return t.toString();
    }
}

LeetCode 152. Maximum Product Subarray

Problem:

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:

DP. Two arrays store largest and smallest values if the subarray stops at the element. If current value is smaller than 0 then earlier product as small as possible, if greater than 0 then earlier product as large as possible. Finally find largest product from product array.

Beat 98% haha.

public class Solution {
    public int maxProduct(int[] nums) {
        int[] maxs = new int[nums.length];
        int[] mins = new int[nums.length];
        maxs[0] = nums[0]; 
        mins[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] >= 0) {
                maxs[i] = nums[i] > maxs[i-1]*nums[i] ? nums[i] : maxs[i-1]*nums[i];
                mins[i] = nums[i] < mins[i-1]*nums[i] ? nums[i] : mins[i-1]*nums[i];
            }
            else {
                maxs[i] = nums[i] > mins[i-1]*nums[i] ? nums[i] : mins[i-1]*nums[i];
                mins[i] = nums[i] < maxs[i-1]*nums[i] ? nums[i] : maxs[i-1]*nums[i];
            }
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < maxs.length; i++) {
            if (maxs[i] > max) max = maxs[i];
        } 
        return max;
    }
}

LeetCode 49. Group Anagrams

Problem:

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"],
Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Solution:

Use HashMap to make things faster.

public class Solution {
    List<List<String>> result = new ArrayList<List<String>>();
    HashMap<String, List<String>> map = new HashMap<String, List<String>>();
    
    public List<List<String>> groupAnagrams(String[] strs) {
        for (int i = 0; i < strs.length; i++) {
            String sorted = sortString(strs[i]);
            if (!map.containsKey(sorted)) {
                List<String> list = new ArrayList<String>();
                list.add(strs[i]);
                map.put(sorted, list);
            }
            else {
                List<String> list = map.get(sorted);
                list.add(strs[i]);
            }
        }
        for (List<String> list: map.values()) {
            result.add(list);
        }
        return result;
    }
    
    private String sortString(String s) {
        char[] chars = s.toCharArray();
        Arrays.sort(chars);
        return String.valueOf(chars);
    }
}