Tag: c++

Given the integers zero, one, low, 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.

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

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

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

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Solution:

#include <string>
#include <vector>
#include <iostream>
#include <functional> // Include this for std::function

using namespace std;

vector<string> generateParenthesis(int n) {
    vector<string> solutions;

    // Explicitly declare the lambda with std::function
    function<void(string, int, int)> backtrack = [&](const string& current, int open, int close) {
        if (current.length() == n * 2) {
            solutions.push_back(current);
            return;
        }
        if (open < n) {
            backtrack(current + '(', open + 1, close);
        }
        if (close < open) {
            backtrack(current + ')', open, close + 1);
        }
    };

    // Start the backtracking
    backtrack("", 0, 0);

    return solutions;
}

// Main function
int main() {
    int n = 3; // Example input
    vector<string> result = generateParenthesis(n);
    cout << "Number of solutions: " << result.size() << endl;
    // Print the results
    for (const auto &str: result) {
        cout << str << endl;
    }

    return 0;
}

Main Takeaways

You have to start with an open parentheses. So the logic reads to add open parentheses until all of them are exhausted. Then you actually start backtracking and adding a closing parentheses. So for n=2 you get a simple tree like this one below. Watch the video if you need more understanding on how to solve this one.

      o
     /
    /
   (
  / \
 /   \
((    ()
 |    |
(()) ()()

You are given an integer array nums, an integer k, and an integer multiplier.

You need to perform k operations on nums. In each operation:

• Find the minimum value x in nums. If there are multiple occurrences of the minimum value, select the one that appears first.
• Replace the selected minimum value x with x * multiplier.

Return an integer array denoting the final state of nums after performing all k operations.

Approach Using a Min-Heap

We use a priority queue (min-heap) that stores pairs (value, index) to efficiently find the smallest number in the array along with its index.

Steps:

1. Push all elements of nums into the min-heap. Each element is stored as a tuple (value, index) (to preserve the index).
2. Perform k operations:
   • Extract the smallest element (top of the heap) from the min-heap.
   • Update the value at the extracted index in nums by multiplying it with multiplier.
   • Push the updated value (new_value, index) back into the heap.
3. After all k operations, return the modified nums array.

Priority Queue Configuration:

• Since we want to retrieve the smallest element, we configure priority_queue to behave as a min-heap using greater<tuple<int, int>>.

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
using namespace std;

vector<int> getFinalState(vector<int>& nums, int k, int multiplier) {
    // Min-heap to store pairs of (value, index)
    priority_queue<tuple<int, int>, vector<tuple<int, int>>, greater<tuple<int, int>>> minHeap;

    // Step 1: Push all elements into the min-heap
    for (int i = 0; i < nums.size(); i++) {
        minHeap.push({nums[i], i});
    }

    // Step 2: Perform k operations
    for (int i = 0; i < k; i++) {
        // Extract the smallest element from the min-heap
        auto [value, index] = minHeap.top(); // Get the top element (smallest)
        minHeap.pop(); // Remove it from the heap

        // Update the value in the original array
        nums[index] = value * multiplier;

        // Push the updated value back into the min-heap
        minHeap.push({nums[index], index});
    }

    // Step 3: Return the modified array
    return nums;
}

int main() {
    vector<int> nums = {2, 3, 1, 5, 1}; // Example array
    int k = 2;                          // Number of operations
    int multiplier = 4;                 // Multiplier

    vector<int> result = getFinalState(nums, k, multiplier);

    // Output the result
    for (int num : result) {
        cout << num << " ";
    }

    return 0;
}

Explanation of the Code:

1. Heap Initialization:
   • All elements in nums are pushed into the min-heap along with their respective indices. This ensures that when we extract the minimum element, we also know its index in the original array.
2. Perform k Operations:
   • For each operation, the smallest value from the heap is fetched (using minHeap.top()).
   • This value is updated (multiplied by multiplier) in the nums array.
   • The updated value, along with the same index, is reinserted into the heap to maintain the order of elements.
3. Final State:
   • After k operations, the array nums is modified, and we return it.

Complexity Analysis:

1. Time Complexity:
   • Building the initial heap: O(n log n) (inserting n elements into the heap).
   • For each of the k operations:
     • Extract the minimum: O(log n)
     • Reinsert the updated value: O(log n).
   • Total: O(n log n + k log n).
   • In most cases, if k is small relative to n, the runtime is dominated by O(n log n).
2. Space Complexity:
   • The priority queue (min-heap) uses O(n) space to store all the elements.