Coding Patterns & Algorithms Cheat Sheet
Uploaded by
latika.shelar69Coding Patterns & Algorithms Cheat Sheet
Uploaded by
latika.shelar69Common questions
Powered by AIPrefix sums optimize subarray sum queries by enabling constant-time lookups for any subarray sum. For problems like 'Continuous Subarray Sum', they provide rapid access to cumulative sums at any given point, allowing the quick calculation of subarray sums by subtracting relevant prefix sums. This reduces time complexity significantly from O(n^2) to O(n) for single queries .
The two-pointer technique simplifies finding pair sums in a sorted array by initializing two pointers at the beginning and end of the array. By advancing or retreating these pointers based on the sum comparison, it reduces the problem's time complexity from O(n^2) to O(n). For example, in the 'Two Sum II – Input Array Is Sorted', by moving the left pointer when the sum is less than the target and the right pointer when the sum is more, the correct pair is efficiently located .
Dynamic programming optimizes the 'Longest Increasing Subsequence' problem by breaking it down into overlapping subproblems, remembering intermediate results (i.e., lengths of increasing subsequences ending at different indices). This avoids recalculations, resulting in efficient time complexity of O(n^2) or O(n log n) depending on whether additional structures like binary indexed trees are used. This strategic calculation allows optimal and scalable solutions .
The greedy approach in 'Activity Selection' problem involves selecting the next activity that finishes the earliest among the available ones at each step. This ensures that more activities can fit into the schedule, maximizing the total number selected. By consistently choosing the local optimum (earliest end time), the approach guarantees the global optimum, as later activities can only be considered if earlier ones are not chosen .
Challenges in using dynamic programming for 'Edit Distance' include managing the multi-dimensional DP table given the different operations (insert, delete, modify) possible on strings. These are overcome by structuring the DP table such that each cell represents the minimum edit distance, updating each based on previous results. This complex problem gets simplified to O(mn) time complexity .
Binary search is more efficient than linear search because it exploits the sorted nature of the array to halve the search space with each step, reducing the time complexity to O(log n). In 'Search in Rotated Sorted Array', binary search can be adapted to account for rotation by identifying whether mid-element comparisons fall in the rotated or normal order section, ultimately finding the target efficiently .
Backtracking facilitates combinatorial problems like the N-Queens by exploring all possible configurations while pruning branches that violate constraints (e.g., placing two queens in the same row). This methodic approach ensures all feasible solutions are explored, while unnecessary paths are efficiently discarded, yielding an optimal balance between completeness and efficiency .
The sliding window technique allows for dynamically adjusting the window size to find the desired substring efficiently. It processes each character once, yielding an average time complexity of O(n). A typical challenge is efficiently tracking characters within the current window to ensure no repetitions, often requiring additional data structures such as hash sets for quick lookup .
Divide and conquer algorithms like 'Merge Sort' improve performance by recursively breaking down problems into smaller subproblems, each of which is easier and faster to solve. The merge operations then efficiently combine these solutions in a manner that preserves order, often benefiting from optimal time complexities like O(n log n) compared to the O(n^2) of iterative sorting approaches .
The greedy strategy in 'Minimum Number of Arrows to Burst Balloons' is applied by sorting balloons by their end coordinate and then iteratively selecting the first balloon's end to shoot all overlapping balloons, thereby minimizing arrows. This approach is effective because it aims to burst as many balloons as possible per arrow, reducing the total number needed while ensuring no balloon is missed .