Forem: Jatin Jayadev

Day 57: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:35:36 +0000

Date: November 22, 2024
Hello Everyone,

Today marks Day 57 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I focused on solving two problems: Partition a set into k subsets with equal sums (Backtracking) and Determine if a string contains all permutations of another string.

1. Partition a set into k subsets with equal sums (Backtracking):

Problem:
Given a set of numbers, partition them into k subsets with equal sum.

Explanation:

Use backtracking to explore all possible partitions and check if the sum of k subsets equals the target sum.
If the subsets match the required sum, return true; otherwise, return false.

Implementation:

bool canPartition(vector<int>& nums, int n, int k, int targetSum, vector<int>& subsets) {
    if (k == 0) return true;
    if (targetSum == 0) return canPartition(nums, n, k - 1, targetSum, subsets); 

    for (int i = 0; i < n; ++i) {
        if (subsets[i] + nums[n - 1] <= targetSum) {
            subsets[i] += nums[n - 1];
            if (canPartition(nums, n - 1, k, targetSum, subsets)) return true;
            subsets[i] -= nums[n - 1];
        }
    }

    return false;
}

bool partitionKSubsets(vector<int>& nums, int k) {
    int totalSum = accumulate(nums.begin(), nums.end(), 0);
    if (totalSum % k != 0) return false;

    vector<int> subsets(k, 0);
    int targetSum = totalSum / k;

    return canPartition(nums, nums.size(), k, targetSum, subsets);
}

2. Determine if a string contains all permutations of another string:

Problem:
Given two strings str1 and str2, determine if str1 contains all permutations of str2.

Explanation:

Use character frequency counting and sliding window approach to verify if str1 contains all permutations of str2.
If the frequency count of characters matches between the window size of str2 and str1, then return true.

Implementation:

bool containsPermutation(string str1, string str2) {
    if (str1.size() < str2.size()) return false;

    unordered_map<char, int> freqMap;
    for (char c : str2) freqMap[c]++;

    int left = 0, right = 0, count = str2.size();

    while (right < str1.size()) {
        if (freqMap.find(str1[right]) != freqMap.end()) {
            if (--freqMap[str1[right]] >= 0) count--;
        }

        if (count == 0) return true;

        if (right - left + 1 < str2.size()) right++;
        else {
            if (freqMap.find(str1[left]) != freqMap.end()) {
                if (++freqMap[str1[left]] > 0) count++;
            }
            left++;
            right++;
        }
    }

    return false;
}

Reflection:
Today's challenges required understanding backtracking and string manipulations. The partitioning problem was about ensuring equal partitioning into k subsets, which felt like a well-known subset sum variant. The permutation problem required character frequency checks, and the sliding window technique made it efficient. Both problems were insightful, giving more clarity on how backtracking and window-based approaches work for such problems.

Looking forward to tomorrow’s problems!

Day 56: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:33:22 +0000

Date: November 21, 2024
Hello Everyone,

Today marks Day 56 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Solve the Subset Sum problem (Backtracking) and Find the length of the shortest common supersequence of two strings.

1. Solve the Subset Sum problem (Backtracking):
Problem:
Given a set of integers, determine if there exists a subset whose sum is equal to a given sum S.

Explanation:

Use backtracking to explore all possible subsets and check if their sum equals S.
If a subset's sum matches S, return true.

Implementation:

bool subsetSum(vector<int>& nums, int n, int target) {
    if (target == 0) return true;
    if (n == 0) return false;
    if (nums[n - 1] > target) return subsetSum(nums, n - 1, target);
    return subsetSum(nums, n - 1, target) || subsetSum(nums, n - 1, target - nums[n - 1]);
}

2. Find the length of the shortest common supersequence of two strings:
Problem:
Given two strings X and Y, find the length of their shortest common supersequence (SCS). A supersequence is a sequence that includes both strings as subsequences with the minimum possible length.

Explanation:

Use dynamic programming to solve this by finding the longest common subsequence (LCS) and then adjusting the result based on the length of LCS.
The formula is: SCS_length = len(X) + len(Y) - LCS_length

Implementation:

int shortestCommonSupersequence(string X, string Y) {
    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    // Fill dp table for LCS
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (X[i - 1] == Y[j - 1]) {
                dp[i][j] = 1 + dp[i - 1][j - 1];
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    int lcs_length = dp[m][n];
    return m + n - lcs_length;
}

Reflection:
Today’s problems were a nice blend of backtracking and dynamic programming. The subset sum problem was a good reminder of how powerful backtracking can be, especially when dealing with subsets and combinations. The shortest common supersequence problem was an insightful way to utilize LCS to simplify the overall solution.

Looking forward to tomorrow's challenges!

Day 55: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:29:56 +0000

Date: November 20, 2024
Hello Everyone,

Today marks Day 55 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Solve the Josephus problem (Recursion) and Count all possible palindromic substrings in a string.

1. Solve the Josephus problem (Recursion):
Problem:
In a circle of people, every k-th person is eliminated until only one person remains. Find the position of that last person.

Explanation:

The Josephus problem can be solved using recursion.
If there's only one person, the survivor is at position 0.
Otherwise, the problem reduces to the Josephus problem for n-1 people with k as the step size.

Implementation:

int josephus(int n, int k) {
    if (n == 1) {
        return 0;
    }
    return (josephus(n - 1, k) + k) % n;
}

2. Count all possible palindromic substrings in a string:
Problem:
Given a string, count the number of palindromic substrings. A substring is considered palindromic if it reads the same forward and backward.

Explanation:

Use dynamic programming to keep track of palindromic substrings.
Expand around each center (both odd-length and even-length centers) to check for palindromic substrings.

Implementation:

int countPalindromicSubstrings(string s) {
    int n = s.size();
    int count = 0;

    vector<vector<bool>> dp(n, vector<bool>(n, false));

    for (int i = 0; i < n; ++i) {
        dp[i][i] = true;
        count++;
    }

    for (int i = 0; i < n - 1; ++i) {
        if (s[i] == s[i + 1]) {
            dp[i][i + 1] = true;
            count++;
        }
    }

    for (int len = 3; len <= n; ++len) {
        for (int i = 0; i <= n - len; ++i) {
            int j = i + len - 1;
            if (s[i] == s[j] && dp[i + 1][j - 1]) {
                dp[i][j] = true;
                count++;
            }
        }
    }

    return count;
}

Reflection:
Today’s problems were both interesting! The Josephus problem helped sharpen my recursion skills, while counting palindromic substrings reinforced dynamic programming and pattern matching. Both challenges are common in algorithmic contests, so solving them will be useful in future coding interviews.

Looking forward to the next!

Day 54: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:26:16 +0000

Date: November 19, 2024
Hello Everyone,

Today marks Day 54 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Find the smallest range covering elements from k sorted lists (Sliding Window) and Find the length of the shortest unsorted subarray in an array.

1. Find the smallest range covering elements from k sorted lists (Sliding Window):
Problem:
Given k sorted lists, find the smallest range that includes at least one number from each of the k lists.

Explanation:

Use a min-heap to maintain the current minimum of the current window and track which list each element belongs to.
Iterate through each list, updating the range and ensuring no overlap.

Implementation:

vector<int> findSmallestRange(vector<vector<int>>& nums) {
    int k = nums.size();
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> minHeap;
    int rangeStart = 0, rangeEnd = INT_MAX;
    int currentMax = INT_MIN;

    for (int i = 0; i < k; ++i) {
        minHeap.push({nums[i][0], i, 0});
        currentMax = max(currentMax, nums[i][0]);
    }

    while (true) {
        auto [minVal, listIndex, elementIndex] = minHeap.top(); minHeap.pop();
        if (currentMax - minVal < rangeEnd - rangeStart) {
            rangeStart = minVal;
            rangeEnd = currentMax;
        }

        if (elementIndex + 1 < nums[listIndex].size()) {
            int nextVal = nums[listIndex][elementIndex + 1];
            minHeap.push({nextVal, listIndex, elementIndex + 1});
            currentMax = max(currentMax, nextVal);
        } else {
            break;
        }
    }

    return {rangeStart, rangeEnd};
}

2. Find the length of the shortest unsorted subarray in an array:
Problem:
Given an array, find the length of the shortest subarray that, if sorted, would sort the entire array.

Explanation:

Identify the leftmost and rightmost elements that are out of order.
The length of the shortest subarray is the difference between these indices.

Implementation:

int findUnsortedSubarray(vector<int>& nums) {
    int n = nums.size();
    int left = 0, right = n - 1;

    while (left < n - 1 && nums[left] <= nums[left + 1]) {
        ++left;
    }

    if (left == n - 1) {
        return 0;
    }

    while (right > 0 && nums[right] >= nums[right - 1]) {
        --right;
    }

    int minVal = *min_element(nums.begin() + left, nums.begin() + right + 1);
    int maxVal = *max_element(nums.begin() + left, nums.begin() + right + 1);

    while (left > 0 && nums[left - 1] > minVal) {
        --left;
    }
    while (right < n - 1 && nums[right + 1] < maxVal) {
        ++right;
    }

    return right - left + 1;
}

Reflection:
Today’s problems provided great practice with sliding windows and identifying subarrays that need sorting. The first problem on finding the smallest range covering elements from k sorted lists sharpened my sliding window technique, while the second problem on finding the length of the shortest unsorted subarray gave me a deep understanding of range-based operations and sorting-related algorithms. Both challenges enhanced my problem-solving skills significantly.

Looking forward to more!

Day 53: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:23:47 +0000

Date: November 18, 2024
Hello Everyone,

Today marks Day 53 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Find the row with the maximum number of 1s in a binary matrix and Rearrange a string such that no two adjacent characters are the same.

1. Find the row with the maximum number of 1s in a binary matrix:
Problem:
Given a binary matrix, find the row that contains the maximum number of 1s.

Explanation:

Use a two-pointer approach, where we start from the rightmost column and move leftwards.
If we find a 1, we move left to narrow the possible rows.
If we find a 0, we move downward, skipping those rows as they can’t contain 1s further to the left.

Implementation:

int findMaxOnesRow(vector<vector<int>> &matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();

    int maxRow = -1, maxCount = 0;
    int j = cols - 1;

    for (int i = 0; i < rows; ++i) {
        while (j >= 0 && matrix[i][j] == 1) {
            --j; 
        }
        int countOnes = cols - j - 1;
        if (countOnes > maxCount) {
            maxCount = countOnes;
            maxRow = i;
        }
    }

    return maxRow;
}

2. Rearrange a string such that no two adjacent characters are the same:
Problem:
Given a string, rearrange its characters such that no two adjacent characters are the same.

Explanation:

Count the frequency of each character.
Use a max-heap to always place the most frequent character first, ensuring that no two adjacent characters are the same.
If at any point, we can't place the most frequent character, it’s impossible to rearrange the string accordingly.

Implementation:

string rearrangeString(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    priority_queue<pair<int, char>> maxHeap;
    for (auto &entry : freq) {
        maxHeap.push({entry.second, entry.first});
    }

    string result;
    while (!maxHeap.empty()) {
        auto [count, ch] = maxHeap.top(); maxHeap.pop();
        if (result.empty() || result.back() != ch) {
            result += ch;
            if (--count > 0) {
                maxHeap.push({count, ch});
            }
        } else {
            if (maxHeap.empty()) {
                return "";
            }
            auto [nextCount, nextCh] = maxHeap.top(); maxHeap.pop();
            result += nextCh;
            if (--nextCount > 0) {
                maxHeap.push({nextCount, nextCh});
            }
            maxHeap.push({count, ch});
        }
    }

    return result;
}

Reflection:

Today’s problems tested my understanding of binary search and greedy algorithms. The first problem, finding the row with the maximum number of 1s, was a good exercise in searching and condition checking, while the second problem on rearranging a string required understanding of frequency counts and using a max-heap to ensure no two adjacent characters are the same. Both problems were insightful and helped strengthen my problem-solving skills.

Stay tuned for more updates, and happy coding!

Day 52: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:19:27 +0000

Date: November 15, 2024
Hello Everyone,

Today marks Day 52 of my competitive programming journey. Here’s what I worked on today:

What I Did Today:
I tackled two problems: Find the number of ways to climb n stairs with 1 or 2 steps at a time (Recursion) and Determine if two rectangles overlap on a 2D plane.

1. Find the number of ways to climb n stairs with 1 or 2 steps at a time (Recursion):
Problem:
Given n stairs, find the number of ways to reach the top if you can take 1 or 2 steps at a time.

Explanation:

Use recursion, where the number of ways to reach the n-th step is the sum of the ways to reach the (n−1)-th and (n−2)-th steps.

Base cases:

If n=0, there is 1 way to stay at the ground (do nothing).
If n=1, there is only 1 way (1 step at a time).

Implementation:

int countWaysToClimbStairs(int n) {
    if (n == 0) return 1;
    if (n == 1) return 1;

    return countWaysToClimbStairs(n - 1) + countWaysToClimbStairs(n - 2);
}

2. Determine if two rectangles overlap on a 2D plane:
Problem:
Given two rectangles on a 2D plane, determine if they overlap.

Explanation:

Two rectangles overlap if they have a common area.
Conditions to check for overlap:

One rectangle is to the left of the other (i.e., right edge of one is left of the other’s left edge).
One rectangle is above the other (i.e., bottom edge of one is above the other’s top edge).

Implementation:

struct Rectangle {
    int x1, y1, x2, y2;
};

bool isOverlap(Rectangle r1, Rectangle r2) {
    if (r1.x2 <= r2.x1 || r2.x2 <= r1.x1) return false;
    if (r1.y2 <= r2.y1 || r2.y2 <= r1.y1) return false;
    return true;
}

Reflection:
Today’s problems tested recursion and condition-checking. The climbing stairs problem with 1 or 2 steps was an insightful use of recursion, while the rectangle overlap problem required geometry-based checks and simple logical conditions. Both exercises improved my understanding of recursion and basic geometry.

Stay tuned for more updates, and happy coding!

Day 51: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:16:38 +0000

Date: November 14, 2024
Hello Everyone,

Today marks Day 51 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Generate all balanced parentheses of length 2n and Find the longest common subsequence between two strings.

1. Generate all balanced parentheses of length 2n (Backtracking):
Problem:
Given a number n, generate all combinations of n pairs of balanced parentheses.

Explanation:

Use recursion and backtracking to build the combinations.
Track the number of open and close parentheses to ensure balance.

Implementation:

void generateParentheses(int open, int close, string current, vector<string>& result) {
    if (open == 0 && close == 0) {
        result.push_back(current);
        return;
    }

    if (open > 0) {
        generateParentheses(open - 1, close, current + "(", result);
    }

    if (close > open) {
        generateParentheses(open, close - 1, current + ")", result);
    }
}

vector<string> balancedParentheses(int n) {
    vector<string> result;
    generateParentheses(n, n, "", result);
    return result;
}

2. Find the longest common subsequence between two strings (Recursion):
Problem:
Given two strings, find the length of their longest common subsequence.

Explanation:

Use recursion to compare characters from both strings.
If characters match, add 1 and move to the next characters in both strings.
Otherwise, explore both possibilities (skip one character in each string) and take the maximum length.

Implementation:

int longestCommonSubsequence(string s1, string s2, int i, int j) {
    if (i == s1.length() || j == s2.length()) {
        return 0;
    }

    if (s1[i] == s2[j]) {
        return 1 + longestCommonSubsequence(s1, s2, i + 1, j + 1);
    } else {
        return max(longestCommonSubsequence(s1, s2, i + 1, j),
                   longestCommonSubsequence(s1, s2, i, j + 1));
    }
}

Reflection:
Today’s problems were an excellent mix of recursion and backtracking. Generating balanced parentheses was particularly enjoyable as it required creative problem-solving. The longest common subsequence problem strengthened my understanding of recursion and string manipulations.

Stay tuned for more updates, and happy coding!

Day 50: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:13:37 +0000

Date: November 13, 2024
Hello Everyone,

Today marks Day 50 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I tackled two challenging problems: Solve the Knight’s Tour problem and Find the maximum path sum in a binary matrix.

1. Solve the Knight’s Tour problem (Backtracking):
Problem:
Given an N×N chessboard, the goal is to find a sequence of moves for a knight such that it visits every square exactly once.

Explanation:

Use backtracking to try all possible knight moves.
Use a 2D matrix to track the visited squares.
If all squares are visited, print the path; otherwise, backtrack.

Implementation:

bool isSafe(int x, int y, vector<vector<int>>& board) {
    return (x >= 0 && y >= 0 && x < N && y < N && board[x][y] == -1);
}

bool solveKnightTour(int x, int y, int move, vector<vector<int>>& board, vector<int>& dx, vector<int>& dy) {
    if (move == N * N) return true;

    for (int i = 0; i < 8; i++) {
        int nextX = x + dx[i];
        int nextY = y + dy[i];

        if (isSafe(nextX, nextY, board)) {
            board[nextX][nextY] = move;

            if (solveKnightTour(nextX, nextY, move + 1, board, dx, dy)) {
                return true;
            }

            board[nextX][nextY] = -1;
        }
    }
    return false;
}

2. Find the maximum path sum in a binary matrix:
Problem:

Given a binary matrix, find the maximum path sum from any cell in the first row to any cell in the last row, moving only to the cells below, diagonally left below, or diagonally right below.

Explanation:

Use dynamic programming to calculate the maximum path sum for each cell, starting from the top row and propagating downwards.

Implementation:

int maxPathSum(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            int up = matrix[i - 1][j];
            int left = (j > 0) ? matrix[i - 1][j - 1] : 0;
            int right = (j < m - 1) ? matrix[i - 1][j + 1] : 0;

            matrix[i][j] += max({up, left, right});
        }
    }

    return *max_element(matrix[n - 1].begin(), matrix[n - 1].end());
}

Reflection:
Both problems tested my problem-solving and implementation skills. The Knight’s Tour problem emphasized the importance of backtracking, while the matrix problem reinforced dynamic programming concepts.

Stay tuned for more updates, and happy coding!

Day 49: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:10:50 +0000

Date: November 12, 2024
Hello Everyone,

Today marks Day 49 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Count the number of subarrays with a given sum and Find the maximum sum of a subarray using Kadane’s Algorithm.

1. Count the number of subarrays with a given sum (Sliding Window):
Problem:
You are given an array and a target sum. Count the number of subarrays that add up to the target sum.

Explanation:

Use a hashmap to store the cumulative sum at each point in the array.
Check if the difference between the current cumulative sum and the target exists in the hashmap. If it does, that means a subarray with the target sum exists.

Implementation:

int countSubarraysWithSum(vector<int>& nums, int target) {
    unordered_map<int, int> prefixSum;
    int count = 0, currentSum = 0;

    prefixSum[0] = 1;

    for (int num : nums) {
        currentSum += num;

        if (prefixSum.find(currentSum - target) != prefixSum.end()) {
            count += prefixSum[currentSum - target];
        }

        prefixSum[currentSum]++;
    }

    return count;
}

2. Find the maximum sum of a subarray (Kadane’s Algorithm):
Problem:
Given an array, find the maximum possible sum of a subarray.

Explanation:

Use a variable to track the current sum (currentSum) and update the maximum sum (maxSum) whenever currentSum exceeds maxSum.
If currentSum drops below 0, reset it to 0 since a negative sum cannot contribute to a maximum.

Implementation:

int maxSubarraySum(vector<int>& nums) {
    int maxSum = nums[0], currentSum = 0;

    for (int num : nums) {
        currentSum += num;

        if (currentSum > maxSum) {
            maxSum = currentSum;
        }

        if (currentSum < 0) {
            currentSum = 0;
        }
    }

    return maxSum;
}

Reflection:
Today’s problems highlighted the power of efficient algorithms like prefix sums and Kadane's algorithm. It was great to revisit these fundamental yet powerful techniques that are frequently used in competitive programming.

Stay tuned for more updates, and happy coding!

Day 48: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:06:16 +0000

Date: November 11, 2024
Hello Everyone,

Today marks Day 48 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Search an element in a matrix sorted row-wise and column-wise and Find the longest palindromic substring in a string.

1. Search an element in a matrix sorted row-wise and column-wise:
Problem:

You are given an n x m matrix where each row is sorted in ascending order, and each column is also sorted in ascending order. Find whether a given element exists in the matrix.

Explanation:

Start searching from the top-right corner of the matrix.
If the current element is larger than the target, move left.
If the current element is smaller than the target, move down.

Implementation:

bool searchMatrix(vector<vector<int>>& matrix, int target) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    int i = 0, j = cols - 1; 

    while (i < rows && j >= 0) {
        if (matrix[i][j] == target) {
            return true;
        } else if (matrix[i][j] > target) {
            j--;
        } else {
            i++; 
        }
    }

    return false;
}

2. Find the longest palindromic substring in a string:
Problem:
Given a string, find the longest substring that is a palindrome.

Explanation:

Use the "expand around center" approach.
Treat each character as a potential center of a palindrome.
Check for odd- and even-length palindromes by expanding around the center.

Implementation:

string longestPalindrome(string s) {
    int n = s.length();
    int start = 0, maxLength = 1;

    for (int i = 0; i < n; i++) {
        int low = i, high = i;
        while (low >= 0 && high < n && s[low] == s[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            low--;
            high++;
        }

        low = i, high = i + 1;
        while (low >= 0 && high < n && s[low] == s[high]) {
            if (high - low + 1 > maxLength) {
                start = low;
                maxLength = high - low + 1;
            }
            low--;
            high++;
        }
    }

    return s.substr(start, maxLength);
}

Reflection:
Today’s problems challenged my logical thinking, especially in understanding how to navigate a sorted matrix efficiently. The palindrome problem, though classic, is always enjoyable as it combines multiple concepts like pointers and substring operations.

Stay tuned for more updates, and happy coding!

Day 47: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 10:01:57 +0000

Date: November 8, 2024
Hello Everyone,

Today marks Day 47 of my competitive programming journey. Here's what I worked on today:

What I Did Today:
I solved two problems: Find the length of the longest palindrome that can be built using letters from a string and Reverse a string using recursion.

1. Find the length of the longest palindrome that can be built using letters from a string:
Problem:
Given a string, find the length of the longest palindrome that can be constructed using its letters. Characters can appear in any order, but at most one character can have an odd frequency.

Explanation:

Use a frequency count of the characters.
Add all pairs of characters to the palindrome's length.
If any characters have an odd frequency, one of them can be placed in the center of the palindrome.

Implementation:

int longestPalindrome(string s) {
    unordered_map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    int length = 0;
    bool oddFound = false;

    for (auto& [key, value] : freq) {
        length += (value / 2) * 2;
        if (value % 2 == 1) {
            oddFound = true;
        }
    }

    if (oddFound) length += 1;

    return length;
}

2. Reverse a string using recursion:
**Problem:
**Reverse a string using recursion without using any additional data structures.

Explanation:

Swap the first and last characters of the string and recursively process the remaining substring.

Implementation:

void reverseString(string& s, int i, int j) {
    if (i >= j) return; 
    swap(s[i], s[j]);
    reverseString(s, i + 1, j - 1); 
}

Reflection:
Today's problems were straightforward but insightful. I enjoyed implementing the recursive reversal and learning how character frequencies contribute to constructing palindromes. Both were great exercises for logical thinking and recursion.

Stay tuned for more updates, and happy coding!

Day 46: Competitive Programming Journal

Jatin Jayadev — Mon, 16 Dec 2024 09:57:14 +0000

Date: November 7, 2024.
Hello Everyone,

Today marks Day 46 of my competitive programming journey, and I’m here to share my progress.

What I Did Today:
I worked on two problems: Find all possible combinations of k numbers that add up to n (Backtracking) and Determine if a Sudoku board is valid (Matrix).

1. Find all possible combinations of k numbers that add up to n (Backtracking):

Problem:
Given two integers, k (number of elements) and n (target sum), find all unique combinations of k numbers between 1 and 9 that sum to n. Each number can be used only once.

Explanation:

Use backtracking to explore all possible combinations.
Include a number, reduce the target sum, and decrease the count k for the next recursive call.
Backtrack when the target becomes negative or when k reaches zero.

Implementation:

void findCombinations(int k, int n, int start, vector<int>& current, vector<vector<int>>& result) {
    if (n == 0 && k == 0) { 
        result.push_back(current);
        return;
    }

    if (n < 0 || k == 0) return;

    for (int i = start; i <= 9; i++) {
        current.push_back(i);
        findCombinations(k - 1, n - i, i + 1, current, result);
        current.pop_back(); 
    }
}

vector<vector<int>> combinationSum3(int k, int n) {
    vector<vector<int>> result;
    vector<int> current;
    findCombinations(k, n, 1, current, result);
    return result;
}

2. Determine if a Sudoku board is valid (Matrix):
Problem:
Given a partially filled 9x9 Sudoku board, determine if it is valid.

A valid board satisfies these rules:

Each row contains unique digits from 1-9 or empty cells ('.').
Each column contains unique digits from 1-9 or empty cells ('.').
Each 3x3 sub-grid contains unique digits from 1-9 or empty cells ('.').

Explanation:

Use hash sets to track the seen numbers in rows, columns, and sub-grids.
Traverse the board and validate numbers accordingly.

Implementation:

bool isValidSudoku(vector<vector<char>>& board) {
    vector<unordered_set<char>> rows(9), cols(9), grids(9);

    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            char num = board[i][j];
            if (num == '.') continue;

            int gridIndex = (i / 3) * 3 + (j / 3);

            if (rows[i].count(num) || cols[j].count(num) || grids[gridIndex].count(num)) {
                return false;
            }

            rows[i].insert(num);
            cols[j].insert(num);
            grids[gridIndex].insert(num);
        }
    }

    return true;
}

Reflection:
Today's problems tested my ability to implement backtracking and matrix validation efficiently. I enjoyed the logical depth involved in generating combinations and ensuring Sudoku's rules are followed systematically.

Stay tuned for more updates, and as always, happy coding!