General Problem Solving Tips

03 Sep, 2019

An ever growing list of general problem solving tips. A quick read to absorb some nugget size insights. Best consumed prior to beginning your seasonal coding regiment.

General

• When asked to be efficient with space, sometimes the solution may involve sacrificing time. Vice-versa.
• When asked for the first of something, consider that it might be the last of something else.
• When asked to find something between a known maximum and a known minimum, our mind may be tempted by the heap, but a faster solution might be reached with binary search.
• When asked to select items of a specific condition from a set, an easier or more efficient solution may be found by selecting all items that validate for an opposite condition and computing the difference (whitelist vs blacklist).
• There are $2^N$ subsets in any set, so generally a brute force solution that involves working with all possible sets will be inefficient.
• $!N$ is even less efficient than $2^N$. If this is the complexity of your solution, it's probably not the answer.
• While solving a problem, avoid combining multiple conditions into a single evaluation. Instead evaluate conditions separately at first, even if they seem similar. Otherwise you may miss subtle nuances in the base case or initial state. Separate conditions are also generally easier to reason about.

For example, don't do this:

if condition1(A) or condition2(B):
    return false

Instead, do this

if condition1(A):
    return false
if condition2(B):
    return false

Don't do this

if condition1(A) and condition2(B):
    return true

Instead, do this

if condition1(A):
    if condition2(B):
        return true

Arrays

• Is there a relationship between item values and indices?
• Is there a useful pattern among items?
• Is there an easier solution if we sort the array somehow? Note that sorting places your best possible time complexity at O(NLogN).
• See if a path to a solution may not be reached by:
  • sliding windows.
  • two indices traversing the array in opposite directions.
  • reversing the array (or part of the array).
  • slicing the array and adjoining its subparts in different ways.
  • processing part of the array in one way, and then reprocessing it a different way. e.g. sorting it.
  • combining any or many of the above. For instance if asked to rotate the values of an array by K positions in place, you can achieve this by reversing both [0:k] and [k:] subarrays in-place, and then reversing the entire array in place.
• Is there a key item that can be moved to a more convenient location (head or tail-1) to simplify traversal and processing?
• When top and bottom (or maximum or minimum) are mentioned, can a solution be reached using a heap? Or perhaps a double-ended queue?
• When working with a grid don't use i and j or x and y to express coordinates; rather use row and col or r and c.

    for j=0; j=len(rows); j++ {
        for i=0; i=len(cols); i++ {
            workwith(grid[j][i])  // you have to reverse the order
        }
    }

• When working with seemingly two dimensional data, consider whether your solution also really needs two dimensions? For instance, when looking for the location of an item on a grid, you really want to know in which column it's located in a specific row. A simple array may be used, where each index indicates the row, and the value recorded indicates the index in that row. E.g. A[2] = 4 indicates that the item is at the 5th position on the 3rd row.

Tree problems

• If the tree is a BST,
  • be wary of a node's in-order successor and predecessor.
  • you may need to pass down a local maximum and minimum when processing the child node.

Linked List

• If two lists converge at some point, they become the same list.
• When looking for the $Kth$ item in a list, you probably need to have a slow runner and a fast runner.
• If needing to remove an item you probably need to keep track of a previous position.