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

Strings: Making Anagrams

Given two strings,  and , that may or may not be of the same length, determine the minimum number of character deletions required to make  and  anagrams. Any characters can be deleted from either of the strings.

Input Format

The first line contains a single string, .
The second line contains a single string, .

Constraints

• It is guaranteed that  and  consist of lowercase English alphabetic letters (i.e.,  through ).

Output Format

Print a single integer denoting the number of characters you must delete to make the two strings anagrams of each other.

Sample Input

cde
abc

Sample Output

4

Explanation

We delete the following characters from our two strings to turn them into anagrams of each other:

1. Remove d and e from cde to get c.
2. Remove a and b from abc to get c.

We must delete  characters to make both strings anagrams, so we print  on a new line.

Algorithm:

One picture tells it all:

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

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; public class Solution { public static int countDiff(int[] first, int[] second){ if( first.length != second.length ){ return -1; } int count = 0; for(int i = 0; i < first.length; i++ ){ int diff = Math.abs(first[i] - second[i]); count += diff; } return count; } public static int[] countChars(String str){ int[] result = new int[26]; int offset = (int) 'a'; for(int i=0; i < str.length(); i++ ){ char cc = str.charAt(i); result[cc-offset]++; } return result; } public static int numberNeeded(String first, String second) { int[] countF = countChars(first); int[] countS = countChars(second); return countDiff(countF, countS); } public static void main(String[] args) { Scanner in = new Scanner(System.in); String a = in.next(); String b = in.next(); System.out.println(numberNeeded(a, b)); } }