Master DSA One Problem at a Time

 Pascal Vibes — Building Triangles Like a Pro Problem Statement Given an integer numRows , return the first numRows of Pascal's Triangle . Each number in the triangle is the sum of the two numbers directly above it . Example: Input: numRows = 5 Output: [ [ 1 ], [ 1,1 ], [ 1,2,1 ], [ 1,3,3,1 ], [ 1,4,6,4,1 ] ] Best Data Structure for Solving the Problem This is a CLASSIC example of Tabulation-based Dynamic Programming   We're filling a triangle row-by-row where: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] So we’ll use: A 2D List<List<Integer>> (or array of arrays) No need for fancy trees, heaps, or graphs here. Just pure math and memory  Different Approaches (from Brute Force to Optimized) Approach 1: Build Row by Row Using Previous Row This is the “OG” method — intuitive and easy to visualize. Start with [1] For each new row: Add 1 at the start and end In-between values are sum of two values above it class ...

Tree Vibees - XORing to the Max Problem Statement You’re given a tree with n nodes numbered from 0 to n - 1 , and a 0-indexed array nums where nums[i] is the value of the i-th node. You’re also given a positive integer k . You can perform the following operation any number of times: Pick an edge [u, v] and set: nums[u] = nums[u] ^ k nums[v] = nums[v] ^ k Return the maximum possible sum of all nums[i] after performing any number of such operations. Example: Input: nums = [1,2,1], k = 3, edges = [[0,1],[0,2]] Output: 6 Explanation: Choose edge [0,2]: nums becomes [2,2,2] => sum = 6 Best Data Structure for Solving the Problem This is a classic greedy XOR game on a tree. Since any edge can be used, and operations are reversible, the tree structure becomes less important here. So no need to traverse the tree! We mainly need: Arrays and bitwise operations. Optional but interview-valuable: Dynamic Programming on Trees (for variations). Multiple Approaches ...

Zero Array After Queries You are given an integer array nums and a list of queries, where each query is a pair [li, ri] representing a range. Each query allows you to decrement any subset of elements in the range [li, ri] by 1. Your task is to determine if it is possible to make every element in nums equal to zero after applying all queries in order . Example Input: nums = [ 1 , 0 , 1 ] queries = [[0, 2]] Output: true Explanation: We can select indices 0 and 2 and decrement both by 1 to obtain [0, 0, 0] . Best Data Structure for the Job We are working with multiple range updates and need to evaluate coverage over indices. The best choice here is the difference array combined with a prefix sum . It allows efficient range additions and helps track how many times each index is affected by the queries. Different Approaches Approach 1: Brute Force This naive method iterates over every index for every query and performs the decrement operations directly. class Solution {...

Sort Colors  Problem Statement You’re given: An array nums[] of integers, where each value is either: 0 = Red 🟥 1 = White ⚪ 2 = Blue 🔵 You need to sort the array in-place such that the final order is all 0 s, followed by 1 s, then 2 s. No using .sort()   Example Input: nums = [2, 0, 2, 1, 1, 0] Output: [0, 0, 1, 1, 2, 2] Best Data Structure for the Job Simple arrays do the trick! No need to pull out HashMaps or fancy data structures — all you need are: Some pointer magic A while loop A sprinkle of swaps  Different Approaches 1) Brute Force (Don't do this in interviews ) Just count how many 0s, 1s, and 2s exist, then rewrite the array. class Solution { public void sortColors ( int [] nums) { int count0 = 0 , count1 = 0 , count2 = 0 ; for ( int num : nums) { if (num == 0 ) count0++; else if (num == 1 ) count1++; else count2++; } for ( int i ...

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

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