Rotate Image

★☆☆☆☆

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).

Note, a common method to rotate the image

clockwise rotate
first reverse up to down, then swap the symmetry 
1 2 3     7 8 9     7 4 1
4 5 6  => 4 5 6  => 8 5 2
7 8 9     1 2 3     9 6 3

anticlockwise rotate
first reverse left to right, then swap the symmetry
1 2 3     3 2 1     3 6 9
4 5 6  => 6 5 4  => 2 5 8
7 8 9     9 8 7     1 4 7

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

public void swap(int [][] m, int i, int j, int r, int c) {
    int tmp = m[i][j];
    m[i][j] = m[r][c];
    m[r][c] = tmp;
}

Reverse Words in a String II

★★☆☆☆

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

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

Note, reverse the whole string, then reverse each word.

public void reverseWords(char[] cArr) {
    for (int i = 0; i < cArr.length / 2; ++i) 
        swap(cArr, i, cArr.length - 1 - i);
    int begin = 0;
    for (int end = 0; end < cArr.length; ++end) {
        if (cArr[end] != ' ' && end != cArr.length - 1) continue;
        // if ending is not space, make end+1 to be like the extend space at the end
        if (end == cArr.length - 1) end++;
        // the index here is really easy to get wrong, don't use int i = begin here!
        for (int i = 0; i < (end - begin)/2; ++i) 
            swap(cArr, begin + i, end - 1 - i);  // begin + i, end - 1 - i is critical
        begin = end = end + 1;
    }
}

public void swap(char[] cArr, int i, int j) {
    char c = cArr[i];
    cArr[i] = cArr[j];
    cArr[j] = c;
}

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

Do it in-place with O(1) extra space?

public void rotate(int[] nums, int k) {
    k = k % nums.length;
    reverse(nums, 0, nums.length - k - 1);
    reverse(nums, nums.length - k, nums.length - 1);
    reverse(nums, 0, nums.length - 1);
}

public void reverse(int[] nums, int begin, int end) {
    for (int i = 0; i < (end - begin + 1) / 2; ++i) {
        int tmp = nums[begin + i];
        nums[begin + i] = nums[end - i];
        nums[end - i] = tmp;
    }
}

Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead. Do it in O(n) time!

Example 1: Given nums = [1, -1, 5, -2, 3], k = 3, return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2: Given nums = [-2, -1, 2, 1], k = 1, return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

$$sum(i) = \sum_{x=0}^{i}nums[x]$$

$$\sum_{x=i}^{j}nums[x] = sum[j] - sum[i-1]$$

if $$sum[j] - sum[g] = \sum_{x=g+1}^{j}nums[x] = k$$, it has subarray len $$j - g$$

public int maxSubArrayLen(int[] nums, int k) {
    HashMap<Integer, Integer> seen = new HashMap<>();
    int sum = 0, maxLen = 0;
    for (int i = 0; i < nums.length; ++i) {
        sum += nums[i];
        if (sum == k) maxLen = Math.max(maxLen, i + 1);
        if (seen.containsKey(sum - k)) maxLen = Math.max(maxLen, i - seen.get(sum - k));
        if (!seen.containsKey(sum)) seen.put(sum, i);
    }
    return maxLen;
}