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

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.

Posted on

Zigzag string conversion solution in C++

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this

Input: s = "PAYPALISHIRING", numRows = 3 Output: "PAHNAPLSIIGYIR"
P   A   H   N
A P L S I I G
Y   I   R

Input: s = "PAYPALISHIRING", numRows = 4 Output: "PINALSIGYAHRPI"
P     I    N
A   L S  I G
Y A   H R
P     I

Solution

#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string convert(string s, int numRows) {
        int n = s.size();
        if (n == 1 || numRows < 2 || n <= numRows) return s;
        
        string ans;
        
        for (int i = 0; i < numRows; i++) {
            int j = i;
            ans.push_back(s[i]); // First character of the row
            int down = 2 * (numRows - 1 - i); // Downward step size
            int up = 2 * i; // Upward step size
            
            if (up == 0 && down == 0) return s; // If no movement, just return the string
            
            while (j < n) {
                j += down;
                if (j < n && down > 0) ans.push_back(s[j]);
                
                j += up;
                if (j < n && up > 0) ans.push_back(s[j]);
            }
        }
        
        return ans;
    }
};

int main() {
    Solution solution;
    string s = "PAYPALISHIRING"; // Example input
    int numRows = 3; // Example row count
    
    string result = solution.convert(s, numRows);
    cout << "Zigzag Conversion: " << result << endl; // Output the result
    return 0;
}
Posted on

Search Sorted Matrix Solution in C++

The idea here is to implement binary search after discovering the correct row.


#include <bits/stdc++.h>
using namespace std;



class Solution {
  public:
  
  
    // Function to search a given number in row-column sorted matrix.
    bool searchMatrix(vector<vector<int>> &mat, int x) {
        // code here
        vector<int>*row = nullptr;
        int rows = mat.size();
        int cols = mat[0].size();
        
        for( int i = 0; i < rows; i++ ){
            if( mat[i][0] <= x && mat[i][cols-1] >= x ){
                row = &(mat[i]);
                break;
            }
        }
        
        if( row == nullptr ) return false;
        
        auto binarySearch = [row, x]( int low, int high ) -> bool{
            
            while( low <= high ){
                int mid = low + (high-low)/2;
            
                if( (*row)[mid] == x ){
                    return true;
                }else if((*row)[mid] < x ){
                    low =  mid + 1;
                } else {
                    high = mid - 1;
                }
                
            }
            
            return false;
            
        };   
        
        return binarySearch(0, cols -1 );
    }
};

Posted on

LeetCode 543 Diameter of a Binary Tree in C++

Given the root of a binary tree, return the length of the diameter of the tree.

The diameter of a binary tree is the length of the longest path between any two nodes in a tree. This path may or may not pass through the root.

The length of a path between two nodes is represented by the number of edges between them.

Example 1:
Input: root = [1,2,3,4,5] Output: 3
Explanation: 3 is the length of the path [4,2,1,3] or [5,2,1,3].


Example 2:
Input: root = [1,2] Output: 1

Constraints:

-100 <= Node.val <= 100

The number of nodes in the tree is in the range [1, 104].

Solution in C++ with a test case:


#include <iostream>
#include <algorithm>
using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    int result;
    int dfs(TreeNode* root) {
        if (root == nullptr) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        result = max(result, left + right);
        return max(left, right) + 1;
    }

    int diameterOfBinaryTree(TreeNode* root) {
        result = 0;
        dfs(root);
        return result;
    }
};

// Helper function to create a tree
TreeNode* createTree() {
    /*
        Example tree:
                1
               / \
              2   3
             / \
            4   5
    */
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    return root;
}

int main() {
    // Create a sample binary tree
    TreeNode* root = createTree();

    // Create a Solution object
    Solution solution;

    // Call the diameterOfBinaryTree function
    int diameter = solution.diameterOfBinaryTree(root);

    // Output the result
    cout << "Diameter of the binary tree: " << diameter << endl;

    // Clean up memory (optional but good practice)
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}
Posted on

401. Binary Watch

A binary watch has 4 LEDs on the top to represent the hours (0-11), and 6 LEDs on the bottom to represent the minutes (0-59). Each LED represents a zero or one, with the least significant bit on the right.

  • For example, the below binary watch reads "4:51".

Given an integer turnedOn which represents the number of LEDs that are currently on (ignoring the PM), return all possible times the watch could represent. You may return the answer in any order.

The hour must not contain a leading zero.

  • For example, "01:00" is not valid. It should be "1:00".

The minute must consist of two digits and may contain a leading zero.

  • For example, "10:2" is not valid. It should be "10:02".

Example 1:

Input: turnedOn = 1
Output: ["0:01","0:02","0:04","0:08","0:16","0:32","1:00","2:00","4:00","8:00"]

Example 2:

Input: turnedOn = 9
Output: []

Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<String> readBinaryWatch(int turnedOn) {
        List<String> result = new ArrayList<>();

        // Iterate over possible hours (0 to 11)
        for (int hour = 0; hour < 12; hour++) {
            // Iterate over possible minutes (0 to 59)
            for (int minute = 0; minute < 60; minute++) {
                // Count the number of bits turned on
                int bitsOn = Integer.bitCount(hour) + Integer.bitCount(minute);
                
                // If the total bits on matches the turnedOn count
                if (bitsOn == turnedOn) {
                    // Format the time as "H:MM"
                    result.add(String.format("%d:%02d", hour, minute));
                }
            }
        }
        return result;
    }
}