Permutations

Given a collection of distinct 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],
  [3,2,1]
]

Algorithm:

See Combinations. Simply without rule 2. But the IO settings is a little bit different than Combination, which give you n numbers from 1~n and k buckets. In this problem, it gives you a set of predefined numbers. So instead of start with the first number, you start with nums[0]. And you need an additional array to mark the numbers that already show up.

Solution:

class Solution {
  
    void DFS(int[] visited, int[] nums, List<Integer> ans, List<List<Integer>> res)
    {
      if( ans.size() == nums.length ){
        List<Integer> tmp = new ArrayList<Integer>(ans);
        res.add(tmp);
        return;
      }
      for(int i = 0; i < nums.length; i++){
        if( visited[i] == 0 ){
          visited[i] = 1;
          ans.add(nums[i]);
          DFS(visited, nums, ans, res);
          ans.remove(ans.size()-1);
          visited[i] = 0;
        }
      }
    }
    
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<Integer> answer = new ArrayList<Integer>();
        int[] visited = new int[nums.length]; 
        
        DFS(visited, nums, answer, result);
      
        return result;
    }
}

Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

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

Algorithm:

Imagine you have n cards on your hand and each card has a unique number between 1~n. There are k buckets in front of you. You need to drop your cards into the buckets to come up with a combination.

There's only one rule to follow:

Each time you step in front of the ith bucket, you have to increase the number to drop in from last time.

For example, you drop in 1 in the first bucket, next time you step in front of the first bucket, you have to drop in 2.

Say n = 3, k = 2

          

i = 1 : [ 1 ] [ ]      Drop one in the first bucket

i = 2 : [ 1 ] [ 2 ]   => one combination (1, 2)

i = 2 : [ 1 ] [ ]     When the bucket is full, retrieve the card back to your hand

i = 2 : [ 1 ] [ 3 ]   Because you drop in 2 last time, so you drop in 3  => 2nd combination (1, 3)

i = 2 : [ 1 ] [ ]

i = 1 : [ ] [ ]         You can't drop in 4, so step to the first bucket(rest count on i = 2),
                          and retrieve 1 back to your hand

i = 1 : [ 2 ] [ ]      Because you drop in 1 last time at i = 1, so you drop in 2

i = 2 : [ 2 ] [ 1 ]   Since the count were reset, drop in 1 => (2, 1)

i = 2 : [ 2 ] [ ]

i = 2 : [ 2 ] [ 3 ]   Since 2 is not available, drop in 3 => (2, 3)

i = 2 : [ 2 ] [ ]

i = 1 : [ ] [ ]         Reset count for i = 2

i = 1 : [ 3 ] [ 1 ]   => (3, 1)

i = 2 : [ 3 ] [ ]     

i = 2 : [ 3 ] [ 2 ]   => (3, 2)

We notice that the result is actually the permutation of 3 out of 2 elements. So the combination has to divide by k! which is 2 in this case. To achieve the requirement, we have to add one more rule to the algorithm: The number in the bucket has to be bigger than the one in the previous bucket.

Hence, (3, 1), (3, 2) and (2, 1) is not valid

The mathematical calculation for only one rule is Cn_k * k! = n! / (n-k)! = 3! / 1! = 6

The mathematical calculation for two rules is Cn_k = n! / ((n-k)! * k!) = 3! / (2! * 1!) = 3

Solution:

class Solution {
  
    void DFS(int n, int k, int step, List<Integer> ans, List<List<Integer>> res){
      if( ans.size() == k ){
        ArrayList<Integer> temp = new ArrayList<Integer>(ans);
        res.add(temp);
        return;
      }
  
      // Start with step, which implies the 2nd rule
      // i.e. You will get (1,2) but not (2,1)
      // If you want to get all the permutations, you start with i = 1
      for(int i=step; i <= n; i++){
          ans.add(i);
          DFS(n, k, i+1, ans, res);
          ans.remove(ans.size()-1);
      }
      
    }
  
    public List<List<Integer>> combine(int n, int k) {
      List<List<Integer>> result = new ArrayList<List<Integer>>();
      List<Integer> answer = new ArrayList<Integer>();
      
      DFS(n, k, 1, answer, result);
      
      return result;
        
    }
}

Performance:

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

Algorithm:

The classic fast & slow pointer problem

Just like the clock has 3 hands with different speed.

If there's a cycle, they will meet eventually.

Solutions:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            
            if (slow == fast) return true;
        }
        
        return false;
        
    }
}

Performance:

More intuitively, is to save each node reference in a HashSet (Sorted unique elements hash table).
Return true if found a duplicate. But this method takes more time(Around 10 ms) and need extra space.

Solution 2:

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> mySet = new HashSet<ListNode>();
        while(head != null){
            if(mySet.contains(head)){
                return true;
            }
            else{
                mySet.add(head);
                head = head.next;
            }
        }
        return false;
    }
}

Rotate Image

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

Rotate the image by 90 degrees (clockwise).

Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOTallocate another 2D matrix and do the rotation.

Example 1:

Given input matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

Example 2:

Given input matrix =
[
  [ 5, 1, 9,11],
  [ 2, 4, 8,10],
  [13, 3, 6, 7],
  [15,14,12,16]
], 

rotate the input matrix in-place such that it becomes:
[
  [15,13, 2, 5],
  [14, 3, 4, 1],
  [12, 6, 8, 9],
  [16, 7,10,11]
]

Algorithm:

It's simply moving numbers around, and you only need to find the rules.

for N = 3, you only need to move the outside edge twice :

1 2 3    a   7 2 1     b     7 4 1

4 5 6  ==> 4 5 6  ==>   8 5 2

7 8 9         9 8 3           9 6 3  

To achieve step a :                                                Note that if we want to rotate left:

tmp = (0, 0)          // Throw 1 in tmp                       tmp = (0, 0)

(0, 0) = (2, 0)       // Replace 1 with 7                     (0, 0) = (0, 2)

(2, 0) = (2, 2)       // Replace 7 with 9                     (0, 2) = (2, 2)

(2, 2) = (0, 2)       // Replace 9 with 3                     (2, 2) = (2, 0)

(0, 2) = tmp         // Replace 3 with 1                     (2, 0) = tmp

Same idea you can get step b :

With these coordinates mapping from step a & b, you can get something like this:

1 2 3 4 5 6 7

for(int i=0; i < nn-1; i++) { int tmp = matrix[0][i]; matrix[0][i] = matrix[nn-1-i][0]; matrix[nn-1-i][0] = matrix[nn-1][nn-1-i]; matrix[nn-1][nn-1-i] = matrix[i][nn-1]; matrix[i][nn-1] = tmp; }

But then you realize that this only rotate the outside rim.

For N=4 :

1    2    3   4                 13   9   5    1           c          13   9  5  1
5    6    7   8       =>     14   6   7    2         ===>     14  10  6  2
9   10  11 12                15  10  11  3                       15  11  7  3
13 14  15 16                16  12  8    4                       16  12  8  4

We need extra loop to move the highlighted area (Step c) :

tmp   =  (1, 1)
(1, 1) =  (2, 1)
(2, 1) =  (2, 2)
(2, 2) =  (1, 2)
(1, 2) =  tmp

It's not hard to figure out the final from here.

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public void rotate(int[][] matrix) { int nn = matrix[0].length; for(int j=0; j < nn/2; j++ ) { for(int i=j; i < nn-1-j; i++) { int tmp = matrix[j][i]; matrix[j][i] = matrix[nn-1-i][j]; matrix[nn-1-i][j] = matrix[nn-1-j][nn-1-i]; matrix[nn-1-j][nn-1-i] = matrix[i][nn-1-j]; matrix[i][nn-1-j] = tmp; } } } }

For comparison, this is the solution for rotate left by 90 degree:

  static void rotateLeft2D(int[][] matrix)
  {
    int nn = matrix[0].length;
    for(int j=0; j < nn/2; j++ ) {
      for(int i=j; i < nn-1-j; i++) {
        int tmp = matrix[j][i];
        matrix[j][i] = matrix[i][nn-1-j];
        matrix[i][nn-1-j] = matrix[nn-1-j][nn-1-i];
        matrix[nn-1-j][nn-1-i] = matrix[nn-1-i][j];
        matrix[nn-1-i][j] = tmp;
      }
    }
  }

Performance:

Rotate Array

Rotate an array of n elements to the right by k steps.

For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]

Algorithm

If you draw a diagram like this and check for the change of indexes, it is fairly simple:

0 1 2 3 4 5 6   -> index                
1 2 3 4 5 6 7   -> Original ( n = 7 )
^^^^^^
5 6 7 1 2 3 4   -> rotate right by 3 (k = 3)
         ^^^^^^

This operation is equivalent to three operations
1. Create a destination array with the same length
1. Copy from position '0' of original to destination '3' of length '4' // 0 -> position k of length n-k
2. Copy from position '4' of original to destination '0' of length '3' // n-k -> position 0 of length k

Solution (Rotate right)

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public void rotate(int[] nums, int k) { if (k > nums.length) k = k % nums.length; int[] result = new int[nums.length]; System.arraycopy(nums, nums.length - k, result, 0, k); System.arraycopy(nums, 0, result, k, nums.length - k); System.arraycopy(result, 0, nums, 0, nums.length); } }

Performance

Same algorithm apply to rotation left
0 1 2 3 4 5 6   -> index
1 2 3 4 5 6 7   -> Original
^^^^
4 5 6 7 1 2 3   -> rotate left by 3
            ^^^^

Solution (Rotate left)

1 2 3 4 5 6 7 8 9 10 11 12 13 14

class Solution { public void rotate(int[] nums, int k) { if (k > nums.length) k = k % nums.length; int[] result = new int[nums.length]; System.arraycopy(nums, k, result, 0, nums.length - k); System.arraycopy(nums, 0, result, nums.length - k, k); System.arraycopy(result, 0, nums, 0, nums.length); } }

Although this solution has space complexity O(n) because I make a copy of the original array.

Here's an solution of space O(1):

Algorithm:

We make use the following properties for rotation right

1 2 3 4 5 6 7
4 3 2 1 5 6 7      1. reverse the first n-k elements
4 3 2 1 7 6 5      2. reverse the last k elements
5 6 7 1 2 3 4      3. reverse the whole array

How about rotate left ?

1 2 3 4 5 6 7
3 2 1 4 5 6 7      1. reverse the first k elements
3 2 1 7 6 5 4      2. reverse the last n-k elements
4 5 6 7 1 2 3      3. reverse the whole array

Solution for rotate right:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

public class Solution { public void rotate(int[] nums, int k) { k %= nums.length; reverse(nums, 0, nums.length - 1); reverse(nums, 0, k - 1); reverse(nums, k, nums.length - 1); } private void reverse(int[] nums, int start, int end) { int temp; while(start < end) { temp = nums[start]; nums[start] = nums[end]; nums[end] = temp; start ++; end --; } } }

The shortcoming is that this algorithm runs quite slow in Java

Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abcdabc" p: "abc"

Output:
[0, 4]

Explanation:
The substring with start index = 0 is "abc", which is an anagram of "abc".
The substring with start index = 4 is "abc", which is an anagram of "abc".

Algorithm:

The idea is to convert the string to the counter array. Take Example 2 for example:
                   a , b, c, ....., z
p: "abc" => [1, 1, 1, ....., 0]   as pCount     // means 'a' appears once, 'b' appears once

To initialize, we take the first slice of window from s: "abcdabc" which is "abc"

window: "abc" => [1, 1, 1, ...., 0] as windowCount

if pcCount == windowCount then we know at index 0 we found a match result = [0]

We apply the same idea to the rest of the sliding windows: bcd, cda, dab, abc

Solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

class Solution { int countEqual(int[] window, int[] target){ // Make sure window and target have the same length if( window.length != target.length ) return -1; int count = 0; for(int i=0; i < window.length; i++){ int diff = Math.abs(window[i] - target[i]); count += diff; } // If return zero, means window and target are identical return count; } int[] countChars(String str){ int[] counter = new int[26]; int offset = (int) 'a'; for(int i=0; i < str.length(); i++){ char cc = str.charAt(i); counter[cc-offset]++; } return counter; } public List<Integer> findAnagrams(String s, String p) { List<Integer> result = new LinkedList<Integer>(); if( p.length() > s.length() ) return result; int[] pCount = countChars(p); // char count view of the first window int[] windowCount = countChars(s.substring(0, p.length())); if( countEqual(pCount, windowCount) == 0) result.add(0); for(int i = 1; i < s.length()-p.length()+1; i++) { String window = s.substring(i, i+p.length()); windowCount = countChars(window); if( countEqual(pCount, windowCount) == 0) result.add(i); } return result; } }

Performance
Has two input with size M, N, the time complexity is O(MN)
space complexity is O(1)

Although the execution speed is quite slow, it is a good algorithm to elaborate during the interview.