TC: O(n*4alpha) optimized using Disjoint Set data structure & bitwise AND op to find min cost of edges & common parents.

Validating a Binary Search Tree (BST) in O(n) time complexity. A BST is valid if for every node, its value is greater than all values in its left subtree and less than all values in its right subtree.

Min capability of k subarrays: O(nlog(Max(nums))) Find min of all max values possible using binary search.

Max Candies Problem: Find max candies that can be allocated to kids from same lot, given candies array and number of kids. Use binary search to find optimal solution.

Count substrings with sum/k or count=k in O(n) time using a sliding window approach with a map to track vowel counts.

Implementing a Word Dictionary using Trie data structure. The `WordDictionary` class uses a Trie to store words and provides methods for adding words and searching for words with wildcards (`.`).

Minimax algorithm for grid game: TC O(n), SC O(n). Robot 1 tries to minimize values collected by Robot 2, who maximizes. Prefix sums used to optimize calculations.

BFS algorithm used to find min cost path in grid with obstacles. Time complexity O(n*mlog(n*m)), space complexity O(m*n).

BFS solution for minimum obstacles: TC:O(n*mlog(n*m)), SC:O(n*m). Dijkstra's algorithm used with priority queue to find shortest path.

Count Stars Between Pipes: Given a string s and ranges a, count stars enclosed between first & last pipes for each range. Use prefix & suffix arrays to find nearest pipes & calculate star counts.

Minimize Xor: Given two numbers, num1 and num2, find the minimum number that can be obtained by performing bitwise operations on num1 to match the bit count of num2.

Count prefix and suffix pairs in a list of words. Brute force: O(n^2*m). Optimal solution using Trie: O(n*m).

Min Operations: Given a string of 1s and 0s, find the minimum number of operations to move all 1s to one side. TC: O(n), SC: O(n)

Find anagrams in string s of length n and pattern p of length k. TC: O(n), SC: O(k) for substrings + O(1) for constant space array.

Calculating prefix sum in O(n) time, then iterating over it to find valid splits also in O(n). Solution returns count of ways to split array.

Create prefix sum matrix O(n*m) time, O(n*m) space. Sum of rectangle is calculated in O(row1+row2) time using prefix sum matrix.

Calculate prefix[] in O(n) and get vowel counts in O(k). Solution: iterate words, update prefix[], then calculate result for each query using prefix[]. Vowel check: a,e,i,o,u.

Calculate prefix sums in O(n) time, then use them to find subarray sums in O(1) time with NumArray class. Prefix[i] stores sum till ith index, making range sum calculation efficient.

Sort jobs by profit in descending order, then schedule as close to deadline as possible. Use a slot array to keep track of assigned jobs and maximize profit.

Erase Overlap Intervals: Sort intervals by end time, remove overlapping ones. Count non-overlapping intervals and return length - count.

Sort balloons by end point, then iterate to find non-overlapping intervals. Count the number of intervals and return as minimum arrows needed.

Min platforms required at railway station: O(nlogn) time complexity. Sort trains by arrival & departure times to minimize platform usage.

SlidingWindow Problem: O(n*100) TC, O(n) SC. Find xth smallest negative num in each window of size k. Use HashMap to store freq of nums[i].

Min operations to make all numbers in array increasing: iterate from end, update lower values with greatest divisor. Return -1 if no possible increase.

Solution: Count substrings with at least k distinct characters. Use sliding window approach, incrementing right pointer and decrementing left pointer when necessary hash values reach threshold.

Optimal approach for counting max or subsets in O(2n) time complexity using backtracking. Memoization also possible but not optimal.

Designing scalable video platform: Estimated 5B videos watched daily, 50GB storage needed. Using Amazon S3 & MongoDB for high availability & fast searches. Implementing CDN, cache & UDP/TCP protocols for efficient streaming.

Merge intervals from two lists in O(nlogn) time, where n is the total number of intervals. Use a single list to combine and sort both input lists, then greedily find overlapping intervals.

Greedy algorithm for jumping problem: Traverse array, find farthest index reachable with current jump, update range and increment count of jumps.

Rate limiters throttle users based on API requests in a given time period. Types include Hard, Soft, and Elastic throttling. Use cases include protecting systems from denial-of-service attacks and optimizing system bandwidth.

Max good number found using dynamic programming and backtracking. O(3!) time complexity.

Solution class counts valid substrings of word1 that can be formed using characters from word2, ensuring frequency of each character in the substring is not more than in word2.

Robbing a binary tree: O(n) time complexity and space complexity using DP map and recursive stack space. Maximize node values by considering or not considering the current node's value.

Circular sorting algorithm rearranges elements to their natural indices. It's useful for identifying duplicates and finding missing elements in an array. Example: [5,4,2,1,3] becomes [1,2,3,4,5].

Subset sum problem solved using memoization. TC: O(n*m), SC: O(n*m) for dp array and O(n+m) stack space.

Max money to rob houses without alerting police: `4`. Rob house 1 (money=1) and then house 3 (money=3). Total amount robbed: `1 + 3 = 4`.

Unique Paths problem solved using DP with TC: O(n*m) and SC: O(n*m) for dp array. Recursive function paths() returns number of unique paths from top-left to bottom-right.

Return combinations making up a total amount. Example: coins=[1,2,5], amount=5 returns 4 (5=5, 5=2+2+1, etc.)

Longest Increasing Subsequence problem solved using dynamic programming with tabulation and memoization methods in Java.

Time complexity of frequencySort is O(n log n) due to priority queue operations, not O(1). It's a constant time complexity for inserting k elements into the priority queue where k ≤ 256.

You can jump to the end of an array if you can reach the last index from any position. This is possible with a top-down approach using dynamic programming and memoization.

Time complexity: O(M∗N) due to grid traversal. Space complexity: O(M∗N) for visited array. Solution uses depth-first search (DFS) traversal of the matrix/graph.

Inorder traversal visits left node then root and finally right node. Solution uses recursive approach to traverse binary tree in order, adding values to a list as it goes.

Divide two integers with O(log2N) time complexity using bitwise operations and handle edge cases for signed numbers.

Optimal approach to find longest substring without repeating chars: TC O(n), SC O(256) using int[] of size 256. Update left pointer when duplicate found, keep track of max window substring.

Kadane's Algorithm finds maximum sum of continuous subarray in O(n) time complexity and O(1) space complexity. It iterates through array, updating current sum and max sum as needed.

The State design pattern changes a class's behavior based on its state. It uses an abstract state and concrete states to alter the context's behavior. Example in Java shows how it works with StartState and EndState classes.

Optimal solution for finding XOR of range 1 to N: use N%4 to determine result in O(1) time complexity. For ranges L-R, find XOR of L-1 and R separately and XOR the results.

Find the unique number in an array using bitwise XOR. TC: O(n), SC: O(1). SingleNumber(int[] nums) { int single = nums[0]; for(int i = 1; i < nums.length; i++) single ^= nums[i]; return single; }

Backtracking approach: exponential time complexity, SC: O(2^n)*(n). Using Bit Manipulation: TC: O(2^n)*n, SC: O(2^n)*n. Generate subsets by considering bit values in nums[].

To find bits to flip, use XOR(start, goal). Count 1s in result using log time complexity.

Recursive approach leads to TLE due to O(2^n) TC. Optimal approach uses memoization with TC: O(nlogn) and SC: O(n^2).

Reducing memory usage by sharing data between similar objects is key to efficient software development. The Flyweight pattern achieves this by separating intrinsic & extrinsic state, improving performance & memory efficiency.

Brute force approach: O(N^2), SC: O(256). Optimal approach: O(n), SC: O(256). Hash table used to keep count of characters.

Command pattern: a request wrapped in an object as command, passed to invoker, executed by corresponding object. Follows OCP & SIP solid principles. Example: stock market with BuyOrder & SellOrder classes.

Observer pattern used for one-to-many relationships where changes to subject notify dependent objects. Example: YouTube Channel and subscribers.

Find largest subarray of consecutive ones with k zeros flipped at most. Two-pointer sliding window pattern solves this problem efficiently in O(n) time complexity.

Maximizing score with k card picks: use two pointers to track left and right sums, updating max sum as needed.

Facade design pattern hides system complexity, providing a simple interface for clients to interact with the system. It abstracts underlying complexities, making it easier to use and maintain.

Builder pattern used for complex object creation with optional attributes. It separates construction and representation, ideal for objects with many variations.

Abstract Factory Pattern creates factories of factories, used when creating objects of different product families. It defines interfaces & concrete implementations for products & creators, ensuring correct UI components based on operating system.

ISP prevents clients from depending on unused methods. Interfaces are segregated into smaller, single-responsibility interfaces like IPrint, IScan & IFax.

Objects should be replaceable with their subtype without affecting code correctness. Inheritance can lead to substitution failures, breaking hierarchy or using "Tell don't ask" principle can solve this issue.

Software components should have 1 responsibility & 1 reason to change, not like Swiss-army knife which does many tasks. Example: Employee class modified to follow SRP.

Floyd Warshall algorithm finds shortest paths from all vertices to all others in a graph, detecting negative cycles. Time complexity: O(n^3), Space complexity: O(n^2).

Bellman-ford algorithm finds single source shortest path in directed graphs with negative edge weights. It also detects negative cycles. Time complexity: O(n*m).

Dijkstra's single source shortest path algorithm finds shortest distances from one source to all other nodes in an undirected graph with non-negative edge weights. Time complexity: O(n+Elogn), space complexity: O(n).