1089. Duplicate Zeros

Given a fixed length array arr of integers, duplicate each occurrence of zero, shifting the remaining elements to the right.

Note that elements beyond the length of the original array are not written.

Do the above modifications to the input array in place, do not return anything from your function.

Example 1:

Input: [1,0,2,3,0,4,5,0]
Output: null
Explanation: After calling your function, the input array is modified to: [1,0,0,2,3,0,0,4]

Example 2:

Input: [1,2,3]
Output: null
Explanation: After calling your function, the input array is modified to: [1,2,3]

Note:

``````1 <= arr.length <= 10000
0 <= arr[i] <= 9
``````

Solution:

```class Solution {
public void duplicateZeros(int[] arr) {
int count  = 0;
for (int i = 0; i < arr.length; i ++){
if (arr[i] == 0){
count ++;
}
}

int offset = count;
for (int i = arr.length - 1; i >= 0; i --){
if (i + offset < arr.length){
arr[i+offset] = arr[i];
}
if (arr[i] == 0){
offset --;
if (i + offset < arr.length){
arr[i+offset] = arr[i];
}
}
}
}
}```

88. Merge Sorted Array

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:

The number of elements initialized in nums1 and nums2 are m and n respectively.
You may assume that nums1 has enough space (size that is equal to m + n) to hold additional elements from nums2.

Example:

Input:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

Output: [1,2,2,3,5,6]

Constraints:

-10^9 <= nums1[i], nums2[i] <= 10^9 nums1.length == m + n nums2.length == n Solution.

```class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// index for m
int im = m -1;
// index for n
int in = n -1;
// index for result
int ir = m + n -1;

for (;ir >= 0; ir --){

if (im < 0){
// If one of the array is all cleared, use the other
nums1[ir] = nums2[in--];
} else if (in < 0){
nums1[ir] = nums1[im--];
} else if (nums1[im] > nums2[in]){
// Otherwise, pick the greater one.
nums1[ir] = nums1[im--];
} else {
nums1[ir] = nums2[in--];
}
}

}
}
```

1170. Compare Strings by Frequency of the Smallest Character

Let’s define a function `f(s)` over a non-empty string `s`, which calculates the frequency of the smallest character in `s`. For example, if `s = "dcce"` then `f(s) = 2` because the smallest character is `"c"` and its frequency is 2.

Now, given string arrays `queries` and `words`, return an integer array `answer`, where each `answer[i]` is the number of words such that `f(queries[i])` < `f(W)`, where `W` is a word in `words`.

Example 1:

Input:

``` queries = ["cbd"], words = ["zaaaz"]
```

Output:

``` [1]
```

Explanation:

``` On the first query we have f("cbd") = 1, f("zaaaz") = 3 so f("cbd") < f("zaaaz").
```

Example 2:

Input:

``` queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
```

Output:

``` [1,2]
```

Explanation:

``` On the first query only f("bbb") < f("aaaa"). On the second query both f("aaa") and f("aaaa") are both > f("cc").
```

Constraints:

• `1 <= queries.length <= 2000`
• `1 <= words.length <= 2000`
• `1 <= queries[i].length, words[i].length <= 10`
• `queries[i][j]``words[i][j]` are English lowercase letters.

Straight forward solution O(q * w)

```class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int[] result = new int[queries.length];
for (int i = 0 ; i < queries.length; i ++){
int score = s(queries[i]);

for (String w : words){
if (s(w) > score){
result[i] ++;
}
}
}
return result;
}

public static int s(String s) {
char min = 'z';
char[] ca = s.toCharArray();
for(char c : ca){
if (c < min){
min = c;
}
if (c == 'a'){
break;
}
}
int r = 0;
for(char c : ca){
if (c == min)
r ++;
}
return r;
}
}```

Optimized solution O (q + w)

since we have `1 <= queries[i].length, words[i].length <= 10`

which means query will have only 10 possible values (limited), so for the result.

so we can use counting.

```class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {

int[] freqCounter = new int[11];
int[] result = new int[queries.length];
for (int i = 0; i < words.length; i++) {
int freq = s(words[i]);
freqCounter[freq]++;
}

for (int i = 1; i < freqCounter.length; i++) {
freqCounter[i] += freqCounter[i - 1];
}
for (int i = 0; i < queries.length; i++) {
int freq = s(queries[i]);
result[i] = words.length - freqCounter[freq];
}

return result;
}

public static int s(String s) {
char min = 'z';
int r = 0;
char[] ca = s.toCharArray();
for(char c : ca){
if (c < min){
r = 1;
min = c;
} else if(c == min) {
r ++;
}

}
return r;
}

}```

1275. Find Winner on a Tic Tac Toe Game

Tic-tac-toe is played by two players A and B on a 3 x 3 grid.

Here are the rules of Tic-Tac-Toe:

• Players take turns placing characters into empty squares (” “).
• The first player A always places “X” characters, while the second player B always places “O” characters.
• “X” and “O” characters are always placed into empty squares, never on filled ones.
• The game ends when there are 3 of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given an array `moves` where each element is another array of size 2 corresponding to the row and column of the grid where they mark their respective character in the order in which A and B play.

Return the winner of the game if it exists (A or B), in case the game ends in a draw return “Draw”, if there are still movements to play return “Pending”.

You can assume that `moves` is valid (It follows the rules of Tic-Tac-Toe), the grid is initially empty and A will play first.

Example 1:

Input:

``` moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
```

Output:

``` "A"
```

Explanation:

``` "A" wins, he always plays first.
"X  "    "X  "    "X  "    "X  "    "```

X

```  "
"   " -> "   " -> " X " -> " X " -> "```

X

``` "
"   "    "O  "    "O  "    "OO "    "OO```

X

```"
```

Example 2:

Input:

``` moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
```

Output:

``` "B"
```

Explanation:

``` "B" wins.
"X  "    "X  "    "XX "    "XXO"    "XXO"    "XX```

O

```"
"   " -> " O " -> " O " -> " O " -> "XO " -> "X```

O

``` "
"   "    "   "    "   "    "   "    "   "    "```

O

```  "
```

Example 3:

Input:

``` moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
```

Output:

``` "Draw"
```

Explanation:

``` The game ends in a draw since there are no moves to make.
"XXO"
"OOX"
"XOX"
```

Example 4:

Input:

``` moves = [[0,0],[1,1]]
```

Output:

``` "Pending"
```

Explanation:

``` The game has not finished yet.
"X  "
" O "
"   "
```

Constraints:

• `1 <= moves.length <= 9`
• `moves[i].length == 2`
• `0 <= moves[i][j] <= 2`
• There are no repeated elements on `moves`.
• `moves` follow the rules of tic tac toe.
```class Solution {
public String tictactoe(int[][] moves) {

for (int a = 0; a <= 1; a++ ){
int[] x = new int[3];
int[] y = new int[3];
int[] v = new int[2];

for (int i = a ; i < moves.length; i += 2){
x[moves[i][0]] ++;
y[moves[i][1]] ++;
if (moves[i][0] == moves[i][1]){
v[0] ++;
}
if (moves[i][0] == 2 - moves[i][1]) {
v[1] ++;
}
}

if (x[0] == 3 || x[1] == 3 ||x[2] == 3 || y [0] == 3 || y [1] == 3|| y [2] == 3 || v[0] == 3 || v[1] == 3){
return a==0? "A":"B";
}
}

return moves.length == 9? "Draw":"Pending";
}
}```

1266. Minimum Time Visiting All Points

On a plane there are `n` points with integer coordinates `points[i] = [xi, yi]`. Your task is to find the minimum time in seconds to visit all points.

You can move according to the next rules:

• In one second always you can either move vertically, horizontally by one unit or diagonally (it means to move one unit vertically and one unit horizontally in one second).
• You have to visit the points in the same order as they appear in the array.

Example 1:

Input:

``` points = [[1,1],[3,4],[-1,0]]
```

Output:

``` 7
```

Explanation:

`One optimal path is`

[1,1]

` -> [2,2] -> [3,3] ->`

[3,4]

`-> [2,3] -> [1,2] -> [0,1] ->`

[-1,0]

```
Time from [1,1] to [3,4] = 3 seconds
Time from [3,4] to [-1,0] = 4 seconds
Total time = 7 seconds```

Example 2:

Input:

``` points = [[3,2],[-2,2]]
```

Output:

``` 5
```

Constraints:

• `points.length == n`
• `1 <= n <= 100`
• `points[i].length == 2`
• `-1000 <= points[i][0], points[i][1] <= 1000`

```class Solution {
public int minTimeToVisitAllPoints(int[][] points) {
int result = 0;
int prev_x = points[0][0];
int prev_y = points[0][1];
for (int i = 1; i < points.length; i ++){
int x = points[i][0];
int y = points[i][1];

int diff_x = Math.abs(x - prev_x);
int diff_y = Math.abs(y - prev_y);

result += Math.min(diff_x,diff_y)+Math.abs(diff_x-diff_y);

prev_x = x;
prev_y = y;
}
return result;
}
}```

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Example 1:

Input:

``[1,2,3,4,5,6,7]` and`

k

` = 3`

Output:

``[5,6,7,1,2,3,4]``

Explanation:

```rotate 1 steps to the right: `[7,1,2,3,4,5,6]` rotate 2 steps to the right: ```[6,7,1,2,3,4,5]
```rotate 3 steps to the right: `[5,6,7,1,2,3,4]````

Example 2:

Input:

``[-1,-100,3,99]` and`

k

` = 2`

Output:

` [3,99,-1,-100]`

Explanation:

` rotate 1 steps to the right: [99,-1,-100,3] rotate 2 steps to the right: [3,99,-1,-100]`

Note:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

In place rotate

```class Solution {

/**
* @param Integer[] \$nums
* @param Integer \$k
* @return NULL
*/
function rotate(&\$nums, \$k) {
\$c = count(\$nums);
\$steps = 0;
\$start = 0;

while(\$steps < \$c){
\$i = \$start;
\$prev = \$nums[\$i];
do{
\$next = (\$i+\$k)%\$c;
\$temp = \$nums[\$next];
\$nums[\$next] = \$prev;
\$prev = \$temp;
\$i += \$k;
\$i = \$i % \$c;
\$steps++;
}while(\$start != \$i);
\$start ++;

}

}
}```

917. Reverse Only Letters

Given a string `S`, return the “reversed” string where all characters that are not a letter stay in the same place, and all letters reverse their positions.

Example 1:

Input:

```"ab-cd"
```

Output:

```"dc-ba"
```

Example 2:

Input:

```"a-bC-dEf-ghIj"
```

Output:

```"j-Ih-gfE-dCba"
```

Example 3:

Input:

```"Test1ng-Leet=code-Q!"
```

Output:

```"Qedo1ct-eeLg=ntse-T!"
```

Note:

1. `S.length <= 100`
2. `33 <= S[i].ASCIIcode <= 122`
3. `S` doesn’t contain `\` or `"`

Straightforward solution.

1. collect letters in reverse order.
2. go through string from beginning, if it’s letter, replace with letter from reverse string, else keep special chars and adjust pointer accordingly
3. of course there’s space for improvement, but not necessary
```<?php
class Solution {

/**
* @param String \$S
* @return String
*/
function reverseOnlyLetters(\$S) {
\$x = '';
\$y = '';
for(\$i = strlen(\$S)-1; \$i >=0; \$i -- ){
if(ctype_alpha(\$S[\$i])){
\$x .= \$S[\$i];
}
}
\$xi = 0;
for(\$i = 0; \$i < strlen(\$S); \$i ++){
if(!ctype_alpha(\$S[\$i])){
\$y .= \$S[\$i];
} else {
\$y .= \$x[\$xi];
\$xi ++;
}

}

return \$y;
}
}

?>```

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input:

``` 123
```

Output:

``` 321
```

Example 2:

Input:

``` -123
```

Output:

``` -321
```

Example 3:

Input:

``` 120
```

Output:

``` 21
```

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231,  231 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

```class Solution {

/**
* @param Integer \$x
* @return Integer
*/
function reverse(\$x) {

\$r =  (int) (strrev(trim(\$x,"+-")) * (\$x>0?1:-1));

if(\$r >  pow(2,31)-1 || \$r < -pow(2,31)){
return 0;
}
return \$r;
}
}```