Category Archives: Leetcode

Leetcode

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];
                }
            }
        }
    }
}

 

Leetcode

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--];
            }
        }
        
    }
}
Leetcode

640. Solve the Equation

Solve a given equation and return the value of x in the form of string “x=#value”. The equation contains only ‘+’, ‘-‘ operation, the variable x and its coefficient.

If there is no solution for the equation, return “No solution”.

If there are infinite solutions for the equation, return “Infinite solutions”.

If there is exactly one solution for the equation, we ensure that the value of x is an integer.

Example 1:

Input: "x+5-3+x=6+x-2"
Output: "x=2"

Example 2:

Input: "x=x"
Output: "Infinite solutions"

Example 3:

Input: "2x=x"
Output: "x=0"

Example 4:

Input: "2x+3x-6x=x+2"
Output: "x=-1"

Example 5:

Input: "x=x+2"
Output: "No solution"



class Solution {
    public String solveEquation(String equation) {
        String[] explodes = equation.split("=");
        
        int coeffX = 0;
        int number = 0;
        int cur  = 0;
        int digit = 0;
        
        boolean left = false;
        
        for (String s : explodes){
            left = !left;
            boolean positive = true;
            
            for (int i = 0; i < s.length(); i ++){
                char c = s.charAt(i);
                
                if (c == '+' || c == '-'){
                    // Push previous integer to number
                    number -= cur*(positive? 1 : -1)*(left? 1 : -1);
                    cur = 0; digit = 0;
                    positive = c == '+';
                    
                } else if(c =='x') {
                    // Push previous coeff of x to coeffX
                    if (digit == 0){
                        // If no coeff, coeff = 1
                        cur = 1;
                    }
                    coeffX += cur*(positive? 1 : -1)*(left? 1 : -1);
                    cur = 0; digit = 0;
                } else {
                    // It's a number.
                    cur = 10 * cur +  Integer.valueOf(s.charAt(i)-'0');
                    digit ++;
                }
            }
            
            // If last in group is a number, redundant
            if (digit > 0){
                number += cur*( ! positive? 1 : -1)*(left? 1 : -1);
                cur = 0; digit = 0;
            }
        }
        
        if (coeffX == 0 && number == 0){
            return "Infinite solutions";
        } else if (coeffX == 0){
            return "No solution";
        }
        return "x="+String.valueOf(number/coeffX);
    }
}

 

Leetcode

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;
    }
    
}

 

Leetcode

1278. Palindrome Partitioning III

You are given a string s containing lowercase letters and an integer k. You need to :

  • First, change some characters of s to other lowercase English letters.
  • Then divide s into k non-empty disjoint substrings such that each substring is palindrome.

Return the minimal number of characters that you need to change to divide the string.

 

Example 1:

Input:

 s = "abc", k = 2

Output:

 1

Explanation:

 You can split the string into "ab" and "c", and change 1 character in "ab" to make it palindrome.

Example 2:

Input:

 s = "aabbc", k = 3

Output:

 0

Explanation:

 You can split the string into "aa", "bb" and "c", all of them are palindrome.

Example 3:

Input:

 s = "leetcode", k = 8

Output:

 0

 

Constraints:

  • 1 <= k <= s.length <= 100.
  • s only contains lowercase English letters.

Failed to build the dp during the contest : ( .   it was quite close

class Solution {
    public int palindromePartition(String s, int k) {
        if (k == s.length()){
            return 0;
        }
        
        int[][] dp = new int[s.length()+1][k+1];
        
        
        for (int i = 0; i <= s.length(); i++)
            for (int j = 0; j <= k; j++)
                dp[i][j] = s.length();
        
        dp[0][0] = 0;
        for (int i = 0; i < s.length(); i ++){
          
            for (int j = 0; j < k; j ++){
                
                for (int len = 1; i + len <= s.length(); len++) {
                    int cost = 0;

                    for (int a = i, b = i + len - 1; a < b; a++, b--){
                        if (s.charAt(a) != s.charAt(b)){
                            cost ++;
                        }
                    }
    

                    dp[i + len][j + 1] = Math.min(dp[i + len][j + 1], dp[i][j] + cost);
                }
            }
        }
        
        return dp[s.length()][k];
    }
    

}

Few things to point out:

  • I initialize each value of dp with s.length(), since it can’t be worse than replacing every chars. Integer.MAX_VALUE will cause an integer overflow while building the dp
Leetcode

1277. Count Square Submatrices with All Ones

Given a m * n matrix of ones and zeros, return how many square submatrices have all ones.

 

Example 1:

Input:

 matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]

Output:

 15

Explanation:

 
There are 10 squares of side 1.
There are 4 squares of side 2.
There is one square of side 3.
Total number of squares = 10 + 4 + 1 = 15

Example 2:

Input:

 matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]

Output:

 7

Explanation:

 
There are 6 squares of side 1.  
There is 1 square of side 2. 
Total number of squares = 6 + 1 = 7

 

Constraints:

  • 1 <= arr.length <= 300
  • 1 <= arr[0].length <= 300
  • 0 <= arr[i][j] <= 1

 

Example:

[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

  1. count single ones
  2. count 2×2
  3. count 3×3
  4. ……

Goal: reduce n x n to (n-1)x(n-1) … to 2×2

Now scan 2×2 block, for each position(i,j) scan (i+1,j) (i,j+1) (i+1, j+1)
[0,1,1,1],
[1,1,1,1],
[0,1,1,1]

if the 2×2 scanning block contains 0, update (i,j) to 0
[0,1,1,1],
[0,1,1,1],
[0,1,1,1]

then we can reduce it by removing (ignoring) the last row and column.

[0,1,1],
[0,1,1]

Then walk through with the 2×2 scanning block again.

the counter could be updated when the whole 2×2 block is 1, OR count number of ones in the next round.

Version A, update counter during 2×2 scan

class Solution {
    public int countSquares(int[][] matrix) {
        int c = 0;
        
        int m  = matrix.length;
        int n  = matrix[0].length;
        
        for (int i = 0; i < m; i ++){
            for (int j = 0; j < n; j ++){
                if (matrix[i][j] == 1){
                    c++;
                } 
            }
        }
        
        
        while (m > 1 && n > 1){
            for (int i = 0; i < m-1; i ++){
                for (int j = 0; j < n-1; j ++){
                    if (  matrix[i][j]     == 0 
                       || matrix[i+1][j]   == 0
                       || matrix[i][j+1]   == 0
                       || matrix[i+1][j+1] == 0)
                    {
                        matrix[i][j] = 0;
                    }  else {
                        c++;
                    }
                }
            }
            // lower m and n (ignoring last row and column)
            m --;
            n --;
        }
        return c;
        
    }
}

 

B, a more compact version, update counter next round, count number of ones.
slightly slower for more loops

 

class Solution {
    public int countSquares(int[][] matrix) {
        int c = 0;
        
        int m  = matrix.length;
        int n  = matrix[0].length;
        
        
        
        while (m > 0 && n > 0){
            
            for (int i = 0; i < m; i ++){
                for (int j = 0; j < n; j ++){
                    if (matrix[i][j] == 1){
                        c++;
                    } 
                }
            }
            
            
            for (int i = 0; i < m-1; i ++){
                for (int j = 0; j < n-1; j ++){
                    if (matrix[i][j] == 0 
                       || matrix[i+1][j] == 0
                       || matrix[i][j+1] == 0
                       || matrix[i+1][j+1] == 0){
                        matrix[i][j] = 0;
                    }
                }
            }
            // lower m and n (ignoring last row and column)
            m --;
            n --;
        }
        return c;
        
    }
}

A: 86-110 ms
B: 160-170 ms

Leetcode

1276. Number of Burgers with No Waste of Ingredients

Given two integers tomatoSlices and cheeseSlices. The ingredients of different burgers are as follows:

  • Jumbo Burger: 4 tomato slices and 1 cheese slice.
  • Small Burger: 2 Tomato slices and 1 cheese slice.

Return [total_jumbo, total_small] so that the number of remaining tomatoSlices equal to 0 and the number of remaining cheeseSlices equal to 0. If it is not possible to make the remaining tomatoSlices and cheeseSlices equal to 0 return [].

 

Example 1:

Input:

 tomatoSlices = 16, cheeseSlices = 7

Output:

 [1,6]

Explantion:

 To make one jumbo burger and 6 small burgers we need 4*1 + 2*6 = 16 tomato and 1 + 6 = 7 cheese. There will be no remaining ingredients.

Example 2:

Input:

 tomatoSlices = 17, cheeseSlices = 4

Output:

 []

Explantion:

 There will be no way to use all ingredients to make small and jumbo burgers.

Example 3:

Input:

 tomatoSlices = 4, cheeseSlices = 17

Output:

 []

Explantion:

 Making 1 jumbo burger there will be 16 cheese remaining and making 2 small burgers there will be 15 cheese remaining.

Example 4:

Input:

 tomatoSlices = 0, cheeseSlices = 0

Output:

 [0,0]

Example 5:

Input:

 tomatoSlices = 2, cheeseSlices = 1

Output:

 [0,1]

 

Constraints:

  • 0 <= tomatoSlices <= 10^7
  • 0 <= cheeseSlices <= 10^7

 

Should be an easy question..

class Solution {
    public List<Integer> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        
        List<Integer> result = new ArrayList<>();
        
        if (tomatoSlices % 2 ==1 || cheeseSlices * 4 < tomatoSlices || cheeseSlices * 2 > tomatoSlices){
            return result;
        }
        
        int x = (tomatoSlices - cheeseSlices*2)/2;
        result.add(x);
        result.add(cheeseSlices-x);
        
        return result;
    }
}

 

Leetcode

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";
    }
}