# The Algorithm of Using a Sliding Window.

A sliding window is an abstract concept commonly used in array/string problems. It is effective to solve problems like finding the Longest subarray/substring following a certain pattern. It uses 2 indices i and j to keep track of start and end of the window respectively.

```Array sequence: 1,2,3,4,5,6,7.
a window of [3,4,5,6] can be indicated by
i-> 2;
j-> 5;```

Here is an example of using this concept:

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given `"abcabcbb"`, the answer is `"abc"`, which the length is 3.

Given `"bbbbb"`, the answer is `"b"`, with the length of 1.

Given `"pwwkew"`, the answer is `"wke"`, with the length of 3. Note that the answer must be a substring`"pwke"` is a subsequence and not a substring.

```class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<Character>();
int i = 0; int j = 0;
int max_len = 0;

while (i < s.length() && j < s.length()){
if(!set.contains(s.charAt(j))){
j++;
max_len = max_len>(j-i)? max_len : (j-i);
}else{
set.remove(s.charAt(i));
i++;
}
}

return max_len;
}
}```

# Find and Delete the N-th Element from End of a Linked List (Java)

Implement a function that finds the nth node in a linked list, counting from the end.

Examples:

head = 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> (null / None)

The third element of head counting from the end is 3.

head2 = 1 -> 2 -> 3 -> 4 -> (null / None)

The fourth element of head2 counting from the end is 1.

If the given n is larger than the number of nodes in the list, return null / None.

Solution 1 (two passes):

Find the link list length first using a function list_len(Node head),  then calculate how many positions needs to be moved to the right from the head node.

```public static Node nthFromLast(Node head, int n) {
System.out.println(len);

if(n>len || len<=0){
return null;
}

while(len>n){
len--;
cur=cur.child;
}

return cur;
}

int count=0;

while(cur!=null){
count++;
cur= cur.child;
}

return count;
}```

This above solution need to iterate the link list twice, the worst running time is O(2n), n is the number of elements in the link list

Solution 2 (one pass):

Create 2 pointers p1 and p2, p2 is the nth position to the right of p1. move p1 and p2 together until p2 reaches the last null, then p1 points to the expected element.

``` public static Node nthFromLast(Node head, int n) {
int shift =n;

if (p2==null){
return null;
}

// shift p2 n positions to the right
while(shift>0){
if (p2==null){
return null;
}
shift--;
p2=p2.child;
}

//shift p2 and p1 together untill p2 reaches null
while(p2!=null){
p1=p1.child;
p2=p2.child;
}

return p1;
}```

This above solution needs to iterate the link list only once, the worst running time is O(n), n is the number of elements in the link list.

To delete the found Nth Node from the End of the Linked List:

Given a linked list, remove the nth node from the end of a list and return its head.

For example,

```Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end,
```

Note:
Given n will always be valid.
Try to do this in one pass.

We know how to find p1. To delete p1, we connect p1’s previous node to p1’s next node and we must keep track of p1’s previous node. Because given n is always valid, there is one corner case we must consider: After shifting p2, now p1 points to the head and p2 points to null:

```1->2->3->Null (n = 3)
1->2->Null    (n = 2)
1->Null       (n = 1)
```

In above case, we just return head.next;

For other cases, we can just shift p2 one more position right, so that when p2 shifts to null, p1 is pointing to the previous node of the one needs to be deleted. The answer is accepted by Leetcode.

``` public static ListNode removeNthFromEnd(ListNode head, int n) {
int count = n;

while (count>0){
p2 = p2.next;
count--;
}

// corner case.
if (p2==null){
}

// shift p2 one more position
p2=p2.next;

while (p2!=null){
p1=p1.next;
p2=p2.next;
}

p1.next = p1.next.next;

}```

# Rotating a 2D Array by 90 Degrees (Java)

The problem is: Implement a function that takes a square 2D array (# columns = # rows = n) and rotates it by 90 degrees. Do not create a separate 2D array for the rotation, it rotates in the 2D array.

Example:

```int a1[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
// rotate(a1, 3) should return:
// [[7, 4, 1],
// [8, 5, 2],
// [9, 6, 3]]```

Example:

```  int a2[][] = {{1, 2, 3, 4},
{5, 6, 7, 8},
{9, 10, 11, 12},
{13, 14, 15, 16}};
// rotate(a2, 4) should return:
// [[13, 9, 5, 1],
// [14, 10, 6, 2],
// [15, 11, 7, 3],
// [16, 12, 8, 4]]```

My method rotates the matrix in the same array and does not need an additional matrix to store temp data. It is different from many other solutions online.

a. The Swap:

Each element in the rotation is changing position with 3 other elements in the 2D array: a->b, b->c, c->d, d->a

``` [?, a, ?, ?]
[?, ?, ?, b]
[d, ?, ?, ?]
[?, ?, c, ?]```

Observation 1: If a={i,j}, then b={j,n-1-i}, c={n-1-i, n-1-j},d={n-1-j,i}

b. Row i:

Each rotation happens in a “ring” (example, a1, a2, a2,  b1, b2, b3….d2, d2), only the first `n-1` elements in the first row needs to be swapped. For example, in this 4 x 4 matrix, I only need to swap a1, a2, a3, with b1, b2, b3. Then swap b1, b2, b3 with c1, c2, c3. and this continues.

``` [a1, a2, a3, b1]
[d3, ??, ??, b2]
[d2, ??, ??, b3]
[d1, c3, c2, c1]```

Observation 2: At each row i, only swap the first `n-1` elements. i changes from `0` to `n-2`, So the outer loop should be for (int i=0; i < n-1; i++):

c. Column j:

Swapping from the outside ring (1’s) to the inner rings (2’s), the number of iteration decrements by 2. For example, in this 4 x 4 Matrix, the outside ring (1’s) has a length of 4, the inner ring (2’s) has a length of 2.

``` [1, 1, 1, 1]
[1, 2, 2, 1]
[1, 2, 2, 1]
[1, 1, 1, 1]```

Observation 3: At ith ring, the column number j starts at ith element and ends at n-1-i th elements. j changes from `i` to `n-2-i` So the inner loop is for (int j=i; j<n-1-i; j++)

Put everything together:

``` public static int[][] rotate(int[][] a, int n) {

for (int i=0; i< n-1; i++){  <--- outer loop
for (int j=i; j<n-1-i; j++){   <--- inner loop
int temp = a[i][j];    <--- do the swapping
a[i][j] = a[n-1-j][i];
a[n-1-j][i] = a[n-1-i][n-1-j];
a[n-1-i][n-1-j] = a[j][n-1-i];
a[j][n-1-i] = temp;
}
}
return a;
}
}```