Cue Direction
| No | Cue | Direction | Explanation |
|---|---|---|---|
| 1 | Input array is sorted | Binary search, Two pointers | Binary search takes advantage of the sorted nature of the array to perform efficient search operations in log(n) time. Two pointers approach can solve problems related to pairs or subsequences in the array efficiently. |
| 2 | Asks for all permutations/subsets | Backtracking | Backtracking is efficient for generating all possible combinations or permutations as it tries out all possibilities by progressively building and then undoing candidates. |
| 3 | Given a tree | DFS, BFS | Depth-First Search (DFS) and Breadth-First Search (BFS) are fundamental traversals used to visit all nodes of a tree/graph. The choice between them depends on the problem context. |
| 4 | Given a graph | DFS, BFS | Same as for trees, DFS and BFS are used to traverse or search in graphs, the choice depends on the specifics of the problem. |
| 5 | Given a linked list | Two pointers | Two pointers can be used in a linked list to solve a variety of problems including detecting cycles, finding middle node, or reverse a linked list, etc. |
| 6 | Recursion is banned | Stack | Stacks can be used to emulate the behavior of recursion (maintaining a call stack) without the need for recursive calls. |
| 7 | Must solve in-place | Swap corresponding values, Store one or more different values in the same pointer | Swapping values and storing different values in the same pointer can be used to modify data structures in-place without requiring extra space. |
| 8 | Asks for maximum/minimum subarray/subset/options | Dynamic programming | Dynamic Programming is used when a problem can be broken down into overlapping sub-problems. It is especially useful when we need to find an optimal solution, such as the maximum or minimum. |
| 9 | Asks for top/least K items | Heap, QuickSelect | Heaps are efficient for maintaining a collection of highest/lowest elements (Heap). QuickSelect is a fast in-place version of the QuickSort algorithm, helpful to find the Kth smallest/largest element. |
| 10 | Asks for common strings | Map, Trie | Maps can be used for efficient lookup and storage of string data. Tries are efficient for problems involving prefixes and can be used to solve a variety of string-based problems. |
| 11 | Comparing the size of numeric elements, with their order being relevant | Monotonic stack | A monotonic stack is a stack where the elements are always in sorted order. |
| 12 | Dealing with arrays containing numbers in a given range and asking to find the duplicates/missing ones etc | Cyclic Sort | The input array contains numbers in the range of 0 to n. Since all numbers are unique, place each number at its correct place, for example, placing 0 at index 0, placing 1 at index 1, and so on. Once we have every number in its correct place, we can iterate the array to find the index which does not have the correct number, and that index will be our missing number. |
| 13 | Frequency / Counter / Duplicates / Common String | Map | PLACE HOLDER - FILL IT LATER |
| 14 | Else | Map/Set for O(1) time & O(n) space, Sort input for O(nlogn) time and O(1) space | When no specific pattern is identified, a Map or Set can provide efficient operations. Sorting the input can also help in many cases, particularly for grouping and searching operations. |
This table serves as a rough guide on choosing an approach to solve different types of problems in computer programming, particularly in programming interviews. The best approach might vary depending on the specifics of the problem, the input size and other constraints. Additionally, these techniques can often be combined in different ways to solve more complex problems.
Refer: Recognizing Cues in Problem Statement to Categorize Problem Classes and update this table.