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
Recursion
Dynamic Programming
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:
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:
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:
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:
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:
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:
领英推荐
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:
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:
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:
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:
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:
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:
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:
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??
Mtech CSE '25 @IIITB
7 个月Keep it up!