Posted on

3174. Clear Digits

You are given a string s. Your task is to remove all digits by doing this operation repeatedly: Delete the first digit and the closest non-digit character to its left. Return the resulting string after removing all digits.

Example 1:

Input: s = “abc”
Output: “abc”

Explanation:

There is no digit in the string.

Example 2:

Input: s = “cb34”
Output: “”

Explanation:

First, we apply the operation on s[2], and s becomes "c4".
Then we apply the operation on s[1], and s becomes "".

Constraints:

  • 1 <= s.length <= 100
  • s consists only of lowercase English letters and digits.
  • The input is generated such that it is possible to delete all digits.

    string clearDigits(string s) {
        stack<char> sc;
        string result = "";
        for( char c : s ){
            if( c >= 48 && c <=57 ){
                sc.pop();
            } else
                sc.push(c);
        }
        while( !sc.empty() ){
            result+= sc.top();
            sc.pop();
        }
        reverse( result.begin(), result.end());
        return result;
    }
Posted on

Tuple with Same Product

Given an array nums of distinct positive integers, return the number of tuples (a, b, c, d) such that a * b = c * d where abc, and d are elements of nums, and a != b != c != d.

Example 1:

Input: nums = [2,3,4,6]
Output: 8
Explanation: There are 8 valid tuples:
(2,6,3,4) , (2,6,4,3) , (6,2,3,4) , (6,2,4,3)
(3,4,2,6) , (4,3,2,6) , (3,4,6,2) , (4,3,6,2)

Example 2:

Input: nums = [1,2,4,5,10]
Output: 16
Explanation: There are 16 valid tuples:
(1,10,2,5) , (1,10,5,2) , (10,1,2,5) , (10,1,5,2)
(2,5,1,10) , (2,5,10,1) , (5,2,1,10) , (5,2,10,1)
(2,10,4,5) , (2,10,5,4) , (10,2,4,5) , (10,2,5,4)
(4,5,2,10) , (4,5,10,2) , (5,4,2,10) , (5,4,10,2)

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10<sup>4</sup>
  • All elements in nums are distinct.
class Solution {
public:
    int tupleSameProduct(vector<int>& nums) {
        uint size = nums.size();
        unordered_map<int, int> mp;

        for( int i = 0; i < size; i++ )
            for( int j = i +1; j< size; j++){
                int prod  = nums[i] * nums[j];
                mp[prod]++;
            }
        
        int res = 0;
        for( auto& [prod, cnt] : mp ){
            int pairs = (cnt *(cnt-1)) / 2;
            res += 8 * pairs;
        }

        return res;
    }
};
Posted on

2270. Number of Ways to Split Array

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        // Keep track of sum of elements on left and right sides
        long long leftSum = 0, rightSum = 0;

        // Initially all elements are on right side
        for (int num : nums) {
            rightSum += num;
        }

        int count = 0;
        // Try each possible split position
        for (int i = 0; i < nums.size() - 1; i++) {
            // Move current element from right to left side
            leftSum += nums[i];
            rightSum -= nums[i];

            // Check if this creates a valid split
            if (leftSum >= rightSum) {
                count++;
            }
        }

        return count;
    }
};

You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

  • The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
  • There is at least one element to the right of i. That is, 0 <= i < n - 1.

Return the number of valid splits in nums.

Example 1:

Input: nums = [10,4,-8,7]
Output: 2
Explanation: 
There are three ways of splitting nums into two non-empty parts:
- Split nums at index 0. Then, the first part is [10], and its sum is 10. The second part is [4,-8,7], and its sum is 3. Since 10 >= 3, i = 0 is a valid split.
- Split nums at index 1. Then, the first part is [10,4], and its sum is 14. The second part is [-8,7], and its sum is -1. Since 14 >= -1, i = 1 is a valid split.
- Split nums at index 2. Then, the first part is [10,4,-8], and its sum is 6. The second part is [7], and its sum is 7. Since 6 < 7, i = 2 is not a valid split.
Thus, the number of valid splits in nums is 2.

Example 2:

Input: nums = [2,3,1,0]
Output: 2
Explanation: 
There are two valid splits in nums:
- Split nums at index 1. Then, the first part is [2,3], and its sum is 5. The second part is [1,0], and its sum is 1. Since 5 >= 1, i = 1 is a valid split. 
- Split nums at index 2. Then, the first part is [2,3,1], and its sum is 6. The second part is [0], and its sum is 0. Since 6 >= 0, i = 2 is a valid split.

Constraints:

  • 2 <= nums.length <= 10<sup>5</sup>
  • -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

Posted on

Subarrays with sum K

Given an unsorted array of integers, find the number of continuous subarrays having sum exactly equal to a given number k.

Examples:

Input: arr = [10, 2, -2, -20, 10], k = -10
Output: 3
Explaination: Subarrays: arr[0...3], arr[1...4], arr[3...4] have sum exactly equal to -10.
Input: arr = [9, 4, 20, 3, 10, 5], k = 33
Output: 2
Explaination: Subarrays: arr[0...2], arr[2...4] have sum exactly equal to 33.
Input: arr = [1, 3, 5], k = 0
Output: 0 Explaination: No subarray with 0 sum.

Constraints:

  • 1 ≤ arr.size() ≤ 105
  • -103 ≤ arr[i] ≤ 103
  • -107 ≤ k ≤ 107
class Solution {
  public:
    int countSubarrays(vector<int> &arr, int k) {

    // unordered_map to store prefix sums frequencies
    unordered_map<int, int> prefixSums;
  
    int res = 0;
    int currSum = 0;

    for (int i = 0; i < arr.size(); i++) {
        
        // Add current element to sum so far.
        currSum += arr[i];

        // If currSum is equal to desired sum, then a new
        // subarray is found. So increase count of subarrays.
        if (currSum == k)
            res++;

        // Check if the difference exists in the prefixSums map.
        if (prefixSums.find(currSum - k) != prefixSums.end())
            res += prefixSums[currSum - k];

        // Add currSum to the set of prefix sums.
        prefixSums[currSum]++;
    }

    return res;

    }
};

Posted on

1678. Goal Parser Interpretation

You own a Goal Parser that can interpret a string command. The command consists of an alphabet of "G""()" and/or "(al)" in some order. The Goal Parser will interpret "G" as the string "G""()" as the string "o", and "(al)" as the string "al". The interpreted strings are then concatenated in the original order.

Given the string command, return the Goal Parser‘s interpretation of command.

Example 1:

Input: command = "G()(al)"
Output: "Goal"
Explanation: The Goal Parser interprets the command as follows:
G -> G
() -> o
(al) -> al
The final concatenated result is "Goal".

Example 2:

Input: command = "G()()()()(al)"
Output: "Gooooal"

Example 3:

Input: command = "(al)G(al)()()G"
Output: "alGalooG"
class Solution {
public:
    string interpret(string command) {
        string result = "";
        for(int i=0; i<command.size(); i++){
            if(command[i] == 'G') result += "G";
            else if(command[i] == '(' && command[i+1] == ')') {
                result += "o";
                i++;
            }
            else if(command[i] == '(' && command.substr(i,4) == "(al)"){
                result += "al";
                i += 3;
            }
        }
        return result;
    }
};

Posted on

2559. Count Vowel Strings in Ranges

You are given a 0-indexed array of strings words and a 2D array of integers queries.

Each query queries[i] = [l<sub>i</sub>, r<sub>i</sub>] asks us to find the number of strings present in the range l<sub>i</sub> to r<sub>i</sub> (both inclusive) of words that start and end with a vowel.

Return an array ans of size queries.length, where ans[i] is the answer to the ith query.

Note that the vowel letters are 'a''e''i''o', and 'u'.

Example 1:

Input: words = ["aba","bcb","ece","aa","e"], queries = [[0,2],[1,4],[1,1]]
Output: [2,3,0]
Explanation: The strings starting and ending with a vowel are "aba", "ece", "aa" and "e".
The answer to the query [0,2] is 2 (strings "aba" and "ece").
to query [1,4] is 3 (strings "ece", "aa", "e").
to query [1,1] is 0.
We return [2,3,0].

Example 2:

Input: words = ["a","e","i"], queries = [[0,2],[0,1],[2,2]]
Output: [3,2,1]
Explanation: Every string satisfies the conditions, so we return [3,2,1].
class Solution {
public:
    vector<int> vowelStrings(vector<string>& words, vector<vector<int>>& queries) {
        vector<int> prefixSum(words.size()+1,0);
        vector<int> result;

        function<bool(char)> isVowel = [](char ch)->bool{
            if( ch == 'a' || ch == 'e' || ch =='i' || ch == 'o' || ch=='u'){
                return true;
            }

            return false;
        };

        int index = 1;
        for( string str:words){
            if( isVowel(str.front()) && isVowel(str.back()) ){
                prefixSum[index] = prefixSum[index-1]+1;
            } else
                prefixSum[index] = prefixSum[index-1];

            index++;
        }
 

        for( auto q: queries ){
          result.push_back( prefixSum[q[1]+1] - prefixSum[q[0]] );
        }

        return result;
    }
};
Posted on

1030. Matrix Cells in Distance Order

You are given four integers rowcolsrCenter, and cCenter. There is a rows x cols matrix and you are on the cell with the coordinates (rCenter, cCenter).

Return the coordinates of all cells in the matrix, sorted by their distance from (rCenter, cCenter) from the smallest distance to the largest distance. You may return the answer in any order that satisfies this condition.

The distance between two cells (r<sub>1</sub>, c<sub>1</sub>) and (r<sub>2</sub>, c<sub>2</sub>) is |r<sub>1</sub> - r<sub>2</sub>| + |c<sub>1</sub> - c<sub>2</sub>|.

Example 1:
Input: rows = 1, cols = 2, rCenter = 0, cCenter = 0
Output: [[0,0],[0,1]]
Explanation: The distances from (0, 0) to other cells are: [0,1]

Example 2:
Input: rows = 2, cols = 2, rCenter = 0, cCenter = 1
Output: [[0,1],[0,0],[1,1],[1,0]]
Explanation: The distances from (0, 1) to other cells are: [0,1,1,2]
The answer [[0,1],[1,1],[0,0],[1,0]] would also be accepted as correct.

Example 3:
Input: rows = 2, cols = 3, rCenter = 1, cCenter = 2
Output: [[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]]
Explanation: The distances from (1, 2) to other cells are: [0,1,1,2,2,3]
There are other answers that would also be accepted as correct, such as [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]].

class Solution {
public:

    vector<vector<int>> allCellsDistOrder(int rows, int cols, int rCenter, int cCenter) {

        queue<pair<int,int>> q;        
        vector<vector<int>> result;

        vector<vector<bool>> visited( rows , vector<bool>(cols, false));        
        vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        q.push({rCenter, cCenter});
        visited[rCenter][cCenter] = true;

        while( !q.empty() ){
            int size = q.size();
            while(size > 0){
                auto [currentRow, currentCol] = q.front();              
                result.push_back({currentRow, currentCol});

                q.pop();
                for (auto [dr, dc] : directions) {
                    int newRow = currentRow + dr;
                    int newCol = currentCol + dc;


                    if( newRow >= 0 && newRow < rows && newCol >=0 && newCol < cols 
                        && !visited[newRow][newCol]){                        
                        q.push({newRow,newCol});
                        visited[newRow][newCol] = true;
                    }
                }
                size--;
            }

        }
        return result;
        
    }
};
Posted on

90% of CS graduates can’t figure this out

Someone important on X posted:

https://x.com/vikhyatk/status/1873033432705712304

i have a very simple question i ask during phone screens: print each level of a tree on a separate line. 90% of CS grad candidates just can’t do it. someone needs to investigate these universities.

half the replies are saying i’m trolling because no one asks questions this simple. the other half are saying it’s a retarded leetcode question, they never have to use trees irl, why is it even relevant because ChatGPT can do it etc.

Solution with Boost Library

#include <boost/property_tree/ptree.hpp>
#include <iostream>
#include <string>
#include <queue>
using namespace std;

void levelOrder(const boost::property_tree::ptree& tree) {
    std::queue<boost::property_tree::ptree> q;
    q.push(tree);

    while (!q.empty()) {
        int levelSize = q.size();
        while (levelSize > 0) {
            boost::property_tree::ptree current = q.front();
            q.pop();

            // Print the value at the current level
            auto val = current.get_value<std::string>("");
            if (val != "")
                std::cout << current.get_value<std::string>("")<<" ";

            // Add children nodes to the queue
            for (const auto& node : current) {
                q.push(node.second);
            }
            --levelSize;
        }
        std::cout << std::endl;  // Newline after printing one level
    }
}

int main() {
    // Create a Boost property tree
    boost::property_tree::ptree tree;

    // Insert elements to mimic a binary tree
    tree.put("root.value", "10");

    // Left child
    tree.put("root.left.value", "5");
    tree.put("root.left.left.value", "3");
    tree.put("root.left.right.value", "7");

    // Right child
    tree.put("root.right.value", "15");
    tree.put("root.right.right.value", "20");

    levelOrder(tree);

    return 0;
}

So I wanted to try out using Boost with CLion. What a nightmare. First the issue of using a flatpak install ruins everything when it comes to integrating with the system.

Second using a property tree was a bad idea. I should have went with a graph. Since the original post on X was talking about to solution with a graphic of a binary tree, I tried the property_tree in boost and I didn’t like the output of the tree still, nor the key value pair structure of it.

I will follow up later with a Breath First Search on a Undirected Graph from Boost library next time.

Posted on

Count Ways To Build Good Strings

Given the integers zeroonelow, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:

  • Append the character '0' zero times.
  • Append the character '1' one times.

This can be performed any number of times.

good string is a string constructed by the above process having a length between low and high (inclusive).

Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 10<sup>9</sup> + 7.

Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation: 
One possible valid good string is "011". 
It can be constructed as follows: "" -> "0" -> "01" -> "011". 
All binary strings from "000" to "111" are good strings in this example.

Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are "00", "11", "000", "110", and "011".

Solution: fastest one is using tabulation dynamic programming technique.

    int countGoodStrings(int low, int high, int zero, int one) {
        int sum[100001];
        sum[0] = 1;
        for (int i = 1; i <= high; i++)
        {
            long long sumCur = 0;
            if (i >= zero)
                sumCur += sum[i-zero];
            if (i >= one)
                sumCur += sum[i-one];
            if (sumCur > 0x3000000000000000ll)
                sumCur %= 1000000007;
            sum[i] = sumCur % 1000000007;
        }

        long long sumTotal = 0;
        for (int i = low; i <= high; i++)
            sumTotal += sum[i];
        return sumTotal % 1000000007;
    }

Way slower approach is to use a map in your code for memoization, and a recursive DFS method.

class Solution {
public:
    int countGoodStrings(int low, int high, int zero, int one) {
        map<int, int> dp;
        long mod = pow(10,9) +7;    
        function<int(int)> dfs = [&](int length) -> int{
            
            if( length > high ) return 0;

            if(dp.find(length) != dp.end() )
                return dp[length];

            int count = ( length >= low) ? 1 : 0;
            count = (count + dfs(length + zero)) % mod;
            count = (count + dfs(length + one)) % mod;
            
            return dp[length] = count;
        };

        return dfs(0);    
    }
};

Posted on

Set Matrix Zeros

class Solution {
  public:
    void setMatrixZeroes(vector<vector<int>> &mat) {
        int n = mat.size();
        int m = mat[0].size();
    
        bool firstRowHasZero = false;
        bool firstColHasZero = false;
    
        // Check if the first row has any zero
        for (int j = 0; j < m; j++) {
            if (mat[0][j] == 0) {
                firstRowHasZero = true;
                break;
            }
        }
    
        // Check if the first column has any zero
        for (int i = 0; i < n; i++) {
            if (mat[i][0] == 0) {
                firstColHasZero = true;
                break;
            }
        }
    
        // Use the first row and column to mark zeros
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][j] == 0) {
                    mat[i][0] = 0;
                    mat[0][j] = 0;
                }
            }
        }
    
        // Update the matrix based on the markers
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (mat[i][0] == 0 || mat[0][j] == 0) {
                    mat[i][j] = 0;
                }
            }
        }
    
        // Update the first row if needed
        if (firstRowHasZero) {
            for (int j = 0; j < m; j++) {
                mat[0][j] = 0;
            }
        }
    
        // Update the first column if needed
        if (firstColHasZero) {
            for (int i = 0; i < n; i++) {
                mat[i][0] = 0;
            }
        }
        
    }
};

The idea here is using the first row and column as a Dynamic Programming table to mark which rows and columns need to be zeroed out.
That being done, then first column and row itself is updated at the end.