Master DSA One Problem at a Time

Rearrange Sequence Problem – Largest Subarray that Can Be Rearranged to Form a Contiguous Sequence Problem Statement: You are given an array of size N containing integers which may not be unique. Your task is to find the size of the largest subarray that can be rearranged to form a strictly contiguous sequence. A contiguous sequence is a set of numbers that are in consecutive order (e.g., [1, 2, 3, 4]). Example 1: Input: 5 4 3 3 1 1 Output: 2 Explanation: The largest subarray that can be rearranged to form a contiguous sequence here is {4, 3} , which can be rearranged to {3, 4} . Best Technique – Brute Force Approach This problem can be solved in several ways. Let's start by breaking down the brute force approach, which works by checking all possible subarrays of the given array. It’s not the most efficient solution, but it’s easy to understand and implement. The key idea is: For every possible subarray, check if it can be rearranged into a contiguous sequence. A contiguous...

Edit Distance Problem – Minimum Operations to Convert One String to Another Problem Statement: You are given two strings S1 and S2 . Your task is to convert S1 to S2 using the following allowed operations: Insert a character Delete a character Replace a character Find the minimum number of operations required to make the transformation. Example 1: Input: S1 = "horse" , S2 = "ros" Output: 3 Explanation: Operations: replace 'h' → 'r', remove 'r', remove 'e' Best Technique – Dynamic Programming This is a classic 2D DP problem. Let dp[i][j] represent the minimum edit distance between the first i characters of S1 and the first j characters of S2 . We build up the solution by comparing characters from both strings and checking for 3 possible operations: insert, delete, replace. Different Approaches: Approach 1: Brute Force (Recursion) Try all possibilities recursively: insert, delete, or replace. This ...

Max Frequency Subarray Problem – Number of Subarrays Where Maximum Appears at Least k Times Problem Statement: You are given an integer array nums[] and a positive integer k . A subarray is a contiguous portion of the array. Your task is to count how many subarrays contain the maximum element of the entire array at least k times . Example 1: Input: nums = [ 1 , 3 , 2 , 3 , 3 ], k = 2 Output: 6 Explanation: Subarrays where the max element (3) appears at least 2 times: [1, 3, 2, 3] [1, 3, 2, 3, 3] [3, 2, 3] [3, 2, 3, 3] [2, 3, 3] [3, 3] Best Technique – Two Pointers (Sliding Window) This problem is efficiently solved using the Two Pointers technique. We maintain a sliding window [left...right] and track how many times the maximum value appears within that window. As soon as it appears at least k times, we know that: All subarrays ending at right and starting at any position from left to right are valid! We use this to add (n - right) valid ...

Subarray Score Problem – Number of Subarrays With Score Less Than k Problem Statement: You are given a positive integer array nums[] and an integer k . A subarray's score is defined as: score = sum(subarray) * length(subarray) Your task is to count the number of non-empty subarrays whose score is strictly less than k . Example 1: Input : nums = [2, 1, 4, 3, 5], k = 10 Output : 6 Explanation : Subarrays with scores less than 10 : [2] → 2 * 1 = 2 [1] → 1 * 1 = 1 [4] → 4 * 1 = 4 [3] → 3 * 1 = 3 [5] → 5 * 1 = 5 [2,1] → (2+1) * 2 = 6 Best Technique – Two Pointers (Sliding Window) This problem is best solved using the Two Pointers (or Sliding Window ) approach, which efficiently tracks the sum of a subarray and its length while iterating through the array. We use two pointers start and end to denote the current window. Expand the window with end , and shrink from start as soon as the score becomes ≥ k . Different Approaches: Approach 1: Bru...

Matrix Chain Multiplication Problem Problem Statement: You are given an array arr[] of length n , where arr[i] represents the dimensions of matrix Ai . The matrix multiplication of matrices A1 , A2 , ..., An is a chain multiplication problem, where the matrices are multiplied in sequence. The goal is to find the minimum number of scalar multiplications required to multiply the entire chain of matrices. Matrix Multiplication Rules: For matrices to be multiplied, the number of columns of the first matrix must be equal to the number of rows of the second matrix. Matrix Ai has dimensions arr[i-1] x arr[i] . For example, if arr[] = [10, 20, 30, 40] , then matrix A1 is 10x20 , matrix A2 is 20x30 , and matrix A3 is 30x40 . Problem Explanation: The problem asks us to find the optimal parenthesization of the matrix chain so that the total number of scalar multiplications is minimized. Example 1: Input: arr = [ 10 , 20 , 30 , 40 , 50 ] Output: 38000 Explanation: We have 4 matric...

Count Fixed-Bound Subarrays — Satisfying MinK and MaxK Problem Statement You are given an array of integers nums and two integers minK and maxK . A fixed-bound subarray of nums is a subarray that satisfies the following conditions: The minimum value in the subarray is equal to minK . The maximum value in the subarray is equal to maxK . Your task is to return the number of fixed-bound subarrays in nums . Example 1: Input : nums = [1, 3, 5, 2, 7, 5], minK = 1, maxK = 5 Output : 2 Explanation : The fixed-bound subarrays are [1, 3, 5] and [1, 3, 5, 2] . Best Technique – Sliding Window + Boundary Tracking This problem can be tricky because you need to ensure the subarray contains both the minimum and maximum values exactly. We can efficiently solve this using a sliding window technique, maintaining boundaries to ensure that the subarrays stay valid. Different Approaches: Approach 1: Brute Force with Set Tracking We could try every possible subarray and check if it m...