Master DSA One Problem at a Time

Minimum Equal Sum – Matching Arrays with Smart Replacements Problem Statement You are given two integer arrays nums1 and nums2 , which may contain zeros. You must replace each 0 with a strictly positive integer (≥ 1) such that the sum of both arrays becomes equal . Your goal is to minimize that common equal sum after all replacements. If there is no way to make the sums equal with any valid replacements, return -1 . Example Input: nums1 = [ 3 , 2 , 0 , 1 , 0 ] nums2 = [ 6 , 5 , 0 ] Output: 12 Explanation: Replace the two zeros in nums1 with 2 and 4 → [3,2,2,1,4] Replace the zero in nums2 with 1 → [6,5,1] Both arrays now sum to 12 . Best Data Structure for the Job This problem is mostly numerical, so there’s no need for complex data structures like trees or heaps. What you do need is: A way to count zeros and compute current sums. Simple math to determine possible ranges. Long data type to handle large sums. Different Approaches Approach 1: Brute Fo...

Next Greater Element – Understanding Element Relationships in Arrays Problem Statement Given two distinct 0-indexed integer arrays nums1 and nums2 , where nums1 is a subset of nums2 , return an array of the next greater element for each element in nums1 corresponding to its position in nums2 . The next greater element of a number x in nums2 is the first greater number to the right of x in nums2 . If it does not exist, return -1 Example Input: nums1 = [4,1,2] nums2 = [1,3,4,2] Output: [-1, 3, -1] Explanation: For 4 , there is no number greater than it to its right in nums2 . For 1 , the next greater number is 3 . For 2 , there is no greater number to the right. Best Data Structure for the Job To efficiently solve this problem, we use a stack in combination with a hash map . The stack helps us track elements in a decreasing order while scanning nums2 from right to left, enabling us to find the next greater element for each number efficiently. The hash map i...

Make All Dominoes the Same – Minimum Rotations Problem Statement: You’re given two integer arrays tops[] and bottoms[] representing domino tiles. Each tile has a top and bottom value between 1 and 6 . You can rotate any domino (i.e., swap tops[i] and bottoms[i] ). Goal: Find the minimum number of rotations needed so that all the values in either the tops or bottoms array are the same. If it’s impossible, return -1 . Example: Input: tops = [ 2 , 1 , 2 , 4 , 2 , 2 ], bottoms = [ 5 , 2 , 6 , 2 , 3 , 2 ] Output: 2 Explanation: Rotate the 2nd and 4th domino so all top values become 2. Best Data Structure for the Job: No advanced data structures are needed here — we rely on simple counters and loops. The smart trick is to focus on just two possible candidates: tops[0] and bottoms[0] . Different Approaches Approach 1: Brute Force Try all numbers from 1 to 6 and check if it's possible to make all tops or all bottoms equal to that number. public class BruteForce...

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...

Count Largest Group — Group Numbers by Digit Sum Problem Statement You're given a positive integer n . Group all numbers from 1 to n based on the sum of their digits . Your task is to find how many groups have the largest size (i.e., most numbers). Input: n = 13  Output: 4  Explanation:  There are 9 groups in total, they are grouped according sum of its digits of numbers from 1 to 13: [1,10], [2,11], [3,12], [4,13], [5], [6], [7], [8], [9]. There are 4 groups with largest size.  Best Technique – Digit Grouping with Hashing / Array Optimization This problem looks simple, but under the hood, it tests your ability to: Understand digit operations Use maps or arrays efficiently Find maximums intelligently Let’s explore multiple ways to solve this, from brute force to optimal, and see how each one helps us understand the problem better. Different Approaches: Approach 1: Brute Force using List Grouping Group every number by the digit sum and store fu...