Master DSA One Problem at a Time

 Path Sum You are given the root of a binary tree and an integer targetSum . Your task is to determine whether the tree has any root-to-leaf path such that adding up all the values along the path equals targetSum . A leaf is a node with no children. Example Input : root = [ 5 , 4 , 8 , 11 , null , 13 , 4 , 7 , 2 , null , null , null , 1 ] targetSum = 22 Output : true This is because the path 5 → 4 → 11 → 2 adds up to 22. Best Data Structure for the Job Binary trees are already built using the classic TreeNode class. We just need: A recursive function to traverse the tree, tracking the remaining target sum. Different Approaches Approach 1: Recursive (Depth-First Search) We use recursion to walk through every path from root to leaf. At each node, we subtract the node’s value from the remaining targetSum , and pass it down the recursive call. When we reach a leaf, we check if the remaining sum equals the leaf’s value. /** * Definition for a binary tree node. * pub...

Same Tree You are given the roots of two binary trees, p and q . Your task is to determine whether the two trees are the same. Two binary trees are considered the same if they are structurally identical and the nodes have the same values . Example Input: p = [ 1 , 2 ] q = [ 1 , null, 2 ] Output: false Constraints The number of nodes in both trees is in the range [0, 100] . -10^4 <= Node.val <= 10^4 Best Data Structure for the Job Trees are already built using the classic TreeNode class. We just need: A recursive function to traverse both trees in parallel. Different Approaches Approach 1: Recursive (Depth-First Search) We traverse both trees simultaneously using recursion. At every node, we compare the values and recursively compare the left and right subtrees. /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } ...

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

 Longest Alternating Hamming Subsequence Problem Statement You're given: An array of distinct strings words[] An array groups[] (only 0s and 1s), same length as words You need to find the longest subsequence of words such that: ✅ Consecutive elements are from different groups ✅ Words are of the same length ✅ And differ by exactly one character (i.e., Hamming Distance = 1 ) Return any one such longest subsequence. Example Input: words = [ "cold" , "cord" , "card" , "ward" , "warm" ] groups = [ 1 , 0 , 1 , 0 , 1 ] Output: [ "cold" , "cord" , "card" , "ward" , "warm" ] Best Data Structure for the Job Arrays and Lists  No need for fancy trees or maps Just a good old DP array and a prev[] tracker to rebuild the subsequence  Different Approaches 1)Brute Force — Try All Subsequences (Exponential Time) class Solution { public List<String> getW...

Longest Alternating Subsequence  Problem Statement You are given: An array of distinct strings words[] A binary array groups[] (values 0 or 1), same length as words Find the longest subsequence of words where consecutive elements have alternating groups values. Return any one such longest subsequence. Example Input: words = [ "a" , "b" , "c" , "d" ] groups = [ 1 , 0 , 1 , 1 ] Output: [ "a" , "b" , "c"] Best Data Structure for the Job Simple arrays and lists work well. Since groups contains only 0 or 1, no complex data structures are required. Different Approaches 1. Brute Force — Try All Subsequences (Exponential Time) Enumerate all subsequences, check if their groups alternate, and return the longest. public List<String> bruteForceLongestAltSubseq (String[] words, int [] groups) { List<String> result = new ArrayList <>(); int n = words.length; int maxLen ...

Modified String Transformation with Custom Rules Problem Statement You're given: A string s consisting of lowercase English letters. An integer t indicating the number of transformation steps. An array nums of size 26 where nums[i] tells how many next consecutive characters to replace each letter 'a' + i with. In each transformation: For a character ch , it transforms into the next nums[ch - 'a'] characters in the alphabet. If it goes past 'z' , it wraps around from 'a' . Your goal: Return the final length of the transformed string after t transformations. Since this can be large, return it modulo 10⁹ + 7 . Example Input: s = "abcyy", t = 2 nums = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2] Transformation: Step 1 → "a" → "b", "b" → "c", ..., "y" → "z" → "bcdzz" Step 2 → "b" → "c", "c" → "d",...

Modified String Transformation  Problem Statement You are given a string s of lowercase English letters and an integer t representing the number of transformation steps. Each transformation proceeds as follows: If a character is 'z' , it is transformed into "ab" (two characters). Any other character ch is replaced with the next character in the English alphabet (e.g., 'a' becomes 'b' , 'b' becomes 'c' , and so on). Your task is to calculate the length of the string after t transformations , modulo 10⁹ + 7 . Example Input: s = "abcyy" t = 2 Output: 7 Explanation: After 1st transformation: "a" → "b" , "b" → "c" , "c" → "d" , "y" → "z" , "y" → "z" → "bcdzz" After 2nd transformation: "b" → "c" , "c" → "d" , "d" → "e" , "z...