Day 06 to 09: Coding Problems

I covered 3 topics in these 4 days which are Sliding Window, Recursion, and Dynamic Programming, and below are the 12 problems:

Sliding Window

1. Longest Substring Without Repeating Characters
2. Max Consecutive Ones III
3. Binary Subarray with Sum
4. Count Number of Nice Subarrays
5. Number of substrings containing all three characters
6. Maximum points you can obtain from cards

Recursion

1. Combination Sum - III
2. Rat in a Maze Problem - I

Dynamic Programming

1. Subsequence with sum K
2. Geek's Training
3. Grid Unique Paths
4. Minimum Path Sum in Grid

Problem 1: Longest Substring Without Repeating Characters

Context

The question asks you to determine the length of the longest substring in a given string s that contains no repeating characters. A substring is a contiguous sequence of characters within a string.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a sliding window and a two-pointer approach combined with a hash map to keep track of the last occurrence of each character. Here's what the code does:

1. Use two pointers (left and right) to represent the current window in the string.
2. Expand the window by moving the right pointer and updating the hash map with the 'right' pointer to represent the recent occurrence of the character.
3. If a character is repeated, move the left pointer to the right of the last occurrence of that character as recorded in the hash map.
4. Keep track of the maximum length of substrings found during this process.

This approach ensures that each character is checked at most twice, resulting in an efficient solution with a time complexity of O(n), where n is the length of the string.

Problem 2: Max Consecutive Ones III

Context

The problem is to find the maximum number of consecutive 1's in a given binary array nums if you are allowed to flip at most k 0's to 1's. The objective is to determine the longest sequence of 1's that can be achieved by flipping up to k zeros in the array.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a sliding window and a two-pointer approach to find the maximum number of consecutive ones. Here's what the code does:

1. Use two pointers (left and right) to represent the current window.
2. Move the right pointer r to include more elements.
3. Track the number of 0's in the current window. If the number of flips needed exceeds k, move the left pointer l to shrink the window until the flips are within the limit.
4. Continuously update the maximum length of valid windows found.
5. After processing the array, return the length of the longest valid window.

The algorithm operates in O(n)O(n)O(n) time complexity by efficiently adjusting the window size to handle up to k 0's.

Problem 3: Binary Subarray with Sum

Context

The problem is to count the number of non-empty contiguous subarrays in a binary array nums that have a sum equal to a given integer goal.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a sliding window and a two-pointer approach to count the number of non-empty subarrays in a binary array nums that have a sum equal to a given integer goal. Here’s what the code does:

helper() function:

1. Computes the number of subarrays with a sum less than or equal to a given value goal.
2. Use two pointers (left and right) to represent the current window.
3. Add elements to the window by moving the right pointer r and updating the current sum.
4. If the sum exceeds goal, adjust the left pointer l to reduce the sum until it is less than or equal to goal.
5. For each position of r, count the number of valid subarrays ending at r by adding r - l + 1 to the count.

Utilizes the helper() function to calculate the number of subarrays with an exact sum of goal by subtracting the count of subarrays with a sum less than goal from those with a sum less than or equal to goal.

This process efficiently computes the number of subarrays with sums up to goal in O(n) time.

Problem 4: Count the Number of Nice Subarrays

Context

The problem is to find the number of continuous subarrays within an integer array nums that contain exactly k odd numbers. A subarray is considered "nice" if it meets this criterion.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a sliding window and a two-pointer approach to count the number of continuous subarrays with exactly k odd numbers in the array nums using the sliding window technique. Here’s what the code does:

helper() function:

1. Calculates the number of subarrays with at most k odd numbers.
2. Use two pointers (left and right) to represent the current window.
3. Expand the window by moving the right pointer r and count the odd numbers within the window.
4. If the count of odd numbers exceeds k, move the left pointer l to reduce the count to k or fewer.
5. For each position of r, count the number of valid subarrays ending at r and update the total count.

Utilizes the helper() function to compute the number of subarrays with exactly k odd numbers by subtracting the count of subarrays with at most k-1 odd numbers from those with at most k odd numbers.

The approach efficiently computes the result with a time complexity of O(n).

Problem 5: Number of Substrings Containing all 3 Characters

Context

The problem is to count the number of substrings in a string s (which only contains the characters 'a', 'b', and 'c') that includes at least one occurrence of each character ('a', 'b', and 'c').

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a sliding window and a two-pointer approach along with an array to keep track of the most recent occurrence of each character. Here's what the code does:

1. Uses a vector hash to store the latest positions of 'a', 'b', and 'c'.
2. Use two pointers (left and right) to represent the current window.
3. Expands the window by moving the right pointer r and adjusts the window size dynamically.
4. For each position r, calculate how many substrings ending at r are valid, and update the count accordingly. It ensures that the substrings counted have at least one occurrence of 'a', 'b', and 'c' by checking the last occurrence indices stored in hash.
5. Return the value of count at the end of the function which represents the total number of valid substrings.

The algorithm processes the string in linear time, O(n), where n is the length of the string.

Problem 6: Maximum Points You Can Obtain from Cards

Context

The problem is to find the maximum score achievable by selecting exactly k cards from a row of cards, where you can only take cards from the beginning or the end of the row. The score is the sum of the points of the selected cards, and the goal is to maximize this score.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a sliding window and a two-pointer approach to efficiently compute the maximum sum of selected cards. Here's what the code does:

1. Start with the sum of the first k cards.
2. Slide the window towards the end of the array by replacing cards from the beginning with those from the end.
3. Update and track the maximum score found during this sliding process.

The approach operates in linear time, O(n), where n is the length of the cardPoints array.

Problem 7: Combination Sum III

Context

The problem is to find all unique combinations of k numbers, using digits from 1 to 9, that sum up to a target value n. Each number can be used at most once. The goal is to return a list of all valid combinations, with each combination appearing only once. The order of the combinations in the result does not matter.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a recursive backtracking approach to explore all possible combinations.. Here's what the code does:

1. helper() function handles the current number (val), the sum of the selected numbers (sum), the number of remaining picks (k), the target sum (n), the current combination (ans), and the list of results (res).
2. For picking the current element, it adds the current number to the combination and continues with the next number.
3. For not picking, it skips the current number and continues with the next number.
4. For Backtracking, it removes the last added number to explore other combinations.
5. Returns a list of unique valid combinations at the end of the function.

This approach ensures that all possible valid combinations are considered, leveraging recursion and backtracking to build up solutions incrementally while exploring all potential valid paths.

Problem 8: Rat in a Maze Problem - I

Context

The problem involves finding all possible paths for a rat to move from the top-left corner (0, 0) to the bottom-right corner (n-1, n-1) in an n x n matrix. The rat can move in four directions: 'U' (up), 'D' (down), 'L' (left), and 'R' (right). Cells in the matrix are either:

• 1 (open for movement), or
• 0 (blocked and impassable).

The path must not revisit any cell, and if there are no valid paths, return an empty list. If the starting cell is 0, the rat cannot move to any other cell.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses a recursive backtracking approach to find all possible paths for a rat to move from the top-left corner (0, 0) to the bottom-right corner (n-1, n-1) in an n x n matrix. Here's what the code does:

1. helper() function explores all possible paths from the current cell (i, j) to the destination (n-1, n-1) and stores valid paths in res.
2. visited 2-D array keeps track of which cells have been visited in the current path to prevent revisiting and looping.
3. dr and dc 1-D array store the row and column changes for each possible movement direction (up, right, down, left).
4. The current movement direction is added to a temporary path string. After exploring the resulting path from that move, it removes the direction from the path string to facilitate backtracking.
5. After exploring all possible moves from the current cell, set visited[i][j] back to false to allow other paths to use this cell.
6. Return the vector res containing all valid paths found.

This approach ensures that all potential paths are explored recursively while keeping track of visited cells and the current path, ultimately providing all valid paths from the source to the destination.

Problem 9: Subsequence with Sum K

Context

The problem requires determining whether there exists a subset of elements within an integer array A of size N such that the sum of the subset equals a given integer K. The solution should return true if such a subset exists and false otherwise.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses Dynamic Programming to determine if there is a subset of elements in an array a of size n that sums up to a given integer k. Here's what the code does:

1. helper() function recursively checks whether a subset with the sum equal to sum can be formed starting from the index ind in the array a.
2. Returns true if sum is 0 (empty subset solution) and returns false if out of bounds.
3. Uses a 2D table dp to store results for subproblems to avoid redundant computations.
4. Check if including the current element helps achieve the target sum.
5. Check if excluding the current element still leads to a valid subset.
6. Returns whether a subset with sum k exists based on the results of recursive exploration.

This approach explores all possible subsets by either including or excluding each element, leveraging the memoization table to store and reuse results of previously computed states to optimize performance.

Problem 10: Geek's Training

Context

The problem involves maximizing Geek's total merit points over several days, given that he can choose from three activities each day: Running, Fighting, and Learning Practice. However, he cannot perform the same activity on two consecutive days. The goal is to find the maximum points he can achieve based on these constraints, using a provided 2D array where each entry represents the points for a specific activity on a specific day.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses Dynamic Programming to find the maximum merit points Geek can accumulate over n days while adhering to the constraint that he cannot perform the same activity on two consecutive days. Here's what the code does:

1. helper() function recursively calculates the maximum points Geek can accumulate from the current day ind to the end of the schedule, given the activity performed on the previous day prev_a.
2. If all days have been processed, return 0 as there are no more days to account for.
3. Check if the result for the current state (ind, prev_a) has already been computed. If so, return the stored result from dp.
4. Check if the current activity i is different from the previous activity prev_a. If it is the first day (prev_a == -1), any activity can be chosen.
5. Calculate the maximum points by choosing the activity i for the current day and recursively compute the maximum points for the next day (ind+1) with activity i as the previous activity.
6. Track the maximum of the computed values with the sum variable.
7. Store the computed maximum value in dp[ind][prev_a+1] for future reference and return it.

The approach recursively explores all activity choices across days while using memoization to efficiently compute the maximum merit points Geek can achieve, ensuring no activity is repeated on consecutive days.

Problem 11: Grid Unique Paths

Context

The problem is to determine the number of unique paths a robot can take from the top-left corner to the bottom-right corner of an m x n grid, where the robot can only move either right or down at each step.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The above code uses Dynamic Programming to calculate the number of unique paths from the top-left corner to the bottom-right corner of an m x n grid, where the robot can only move right or down. Here's what the code does:

1. helper() function recursively computes the number of unique paths from the current cell (row, col) to the destination cell (m-1, n-1).
2. Returns 0 if out of bounds, 1 if at the destination
3. Checks if the result is already computed for the current cell.
4. Computes paths by moving right and down, then combines the results.
5. Return the result from the helper function, which gives the total number of unique paths to the bottom-right corner.

The approach uses a recursive approach with memoization to efficiently compute the number of unique paths from the top-left to the bottom-right corner of an m x n grid, considering only moves to the right or downward.

Problem 12: Minimum Path Sum in Grid

Context

The problem is to find the path from the top-left corner to the bottom-right corner of an m x n grid, where the goal is to minimize the sum of the numbers along the path. The only allowed moves are right or down.

For a detailed description of the problem, click here.

Code Snippet

Explanation of the Code

The given code uses Dynamic Programming to find the minimum path sum from the top-left corner to the bottom-right corner of a grid, where you can only move right or down. Here's what the code does:

1. helper() function recursively computes the minimum path sum from the cell (i, j) to the bottom-right corner of the grid.
2. Returns INT_MAX if out of bounds.
3. Checks if the result is already computed for the current cell.
4. Compute the minimum path sum from the current cell (i, j) by considering the paths that move right and down:
5. Add the value of the current cell grid[i][j] to the minimum of the results from moving down and right.
6. If both moves lead to invalid paths (INT_MAX), just return the current cell's value.
7. Save the computed minimum path sum in dp[i][j] and return it.

The approach recursively computes the minimum path sum from the top-left to the bottom-right corner of the grid using memoization to efficiently optimize the search and avoid redundant calculations.

I apologize for not posting daily updates as initially intended, due to some circumstances. I will now be sharing the content in batches every few days to ensure consistency and quality.

Here are the 3 topics and 12 problems that I solved in 4 days. I look forward to sharing more coding challenges with you tomorrow??