Master DSA One Problem at a Time

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

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

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

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