commonPuzzleStrategies.txt

Two sum puzzle
----------------
Brute force O(n^2)
Two for loops to check every combination.
Work done (n-1, n-2 .. 2) = 0(n^2)

Efficient solution O(n) - With just a single pass.
Two Sum = element 1 + element 2
* Attempt to search for an array element in a separate map.
* If the element does not exists on the map, store the result of sum - element 1. Note if two sum actually exists, the value of sum - element 1 would be element 2.
* If the element about to be inserted actually exists on our map, it implies that the two sum solution actually exists (i.e. we are trying to insert element 2)

Slightly less efficient solution O(nlogn) : nlogn + n
* Sort the array
* Assign two pointers, one(start) points to the start of array, second(end) points to the end of array. 
if (A[start]+A[end] == target) return start,end
if(sum > target) end--
if(sum < target)start++ 
To find all pairs:
For each element in the sorted array, check if there exists (target – element) by doing binary search

Three sum puzzle
----------------
Brute force O(n^3)
Three for loops to check every combination of 3 elements in the array.

Efficient solution O(n^2)
* Sort the array
* 3 sum = a + b + c
* Choose a to be all elements at index i from 0 to (n-3)
* Choose b and c from the remaining i+1 to n-1 
* Moving indexes for b and c based on a + b + c values as follows :
 sort(S);
 for i=0 to n-3 do
    a = S[i];
    start = i+1;
    end = n-1;
    while (start < end) do
       b = S[start]
       c = S[end];
       if (a+b+c == 3sum) then
          output a, b, c;
          // Continue search for all triplet combinations summing to 3sum.
           end = end - 1
       else if (a+b+c > 3sum) then
          end = end - 1;
       else
          start = start + 1;
       end
    end
 end 

Another O(n^2) approach that does not involve sorting is to have all elements of the array in a hash table and finding for each index i and j in the array, we can check whether the hash table contains (3sum - array[i] - array[j]) 
Work done to fill the hash table is O(n), two for loops for choosing every possible i and j in the unsorted array, work done would be O(n^2)(Would be true even if the array is sorted). 

Four sum puzzle
----------------
Brute force O(n^4)
Four for loops to check every combination of 4 elements in the array.

Efficent Approach O(n^3)
* Sort the array
* Note 4sum = a + b + c + d 
* Traverse the array choosing a along the way and solve the problem using 3sum for (4sum -a)

Note using this approach of sorting and reducing the problem to k-1Sum, we can reduce any kSum problem to a time complexity of O(n^(k-1)) 

isPalindrome
--------------
Complexity O(N)
Negative numbers are not considered to be palindromes.
Two methods
1. Reverse the number and compare
Warning : Has potential underflow and overflow cases.
Pseudo code
if x != reverse(x)
	return false
else
	return true

reverse(x)
y=0
while x != 0
	n=x%10
// if ((y > (INT_MAX-n)/10) || ((INT_MIN - y) + n > 0)) return -1 
	y=y*10+n
	x/=10
done
return y

2. Compare the front and last two digits and move inwards
Pseudocode
isPalindrome(x)
powersOfTen=1
for (powersOfTen=1; (x/powersOfTen) >= 10; powersOfTen*=10)

while x != 0
	front = x / powersOfTen
	last = x % 10

	if (front != last)
		return false
	// x % powersOfTen gives all digits minus most significant
	// x / 10 takes away the least significant.
	x = (x % powersOfTen) / 10
	// As the number got trimmed down
	powersOfTen /= 100;
done
return true
	
Powerset
---------
Powerset is exhaustive, it has no linear time complexity. It has inherent exponential time complexity.

Recursive method (Not scalable)
Complexity O(2^N)
Invariant : Each and every element in the set is either part of the powerset solution or not.
Scan the input string or set and at every element, recursively call the function by branching into the following two paths :
i. Including the current element in the solution
ii. The current element is not part of the solution
When we have no more element to scan in our recursive function, print the subset solution built so far.

Iterative method (Scalable only upto the largest datatype)
Complexity O(N*2^N) worse than recursive method.
Notice that binary represenation of numbers 0 to the cardinality of the powerset (2^N) has bits set in positions that could generate the subsets.
Iterate through index 0 to 2^(Set size)
Check the bit pattern in index and correspondingly choose the element from set to build a subset.
Notice the N in O(N*2^N) comes from this algorithm checking the bit pattern which should match the set size. So choose your datatype to iterate through 0 to 2^N carefully. 

All Possible Balanced Parentheses
------------------------------------
The # of all possible balanced paranthesis follows the catalan number sequence
Formula (2n)!/((n+1)!n!) for n>=0

Recursive method (Not scalable) 
Have not deduced the complexity.

Invariant : The invariant for balanced parentheses is that at any point in our construction the # left parantheses should be greater or equal than the # right parentheses; so that we may avoid constructing ()) or )()

We are going to build our solution recursively by decrementing left and right parentheses that are allowed to be used.

If # left and # right parentheses is 0, we print the solution constructed so far and exit
When # left parentheses is greater than 0, keep on adding "(" to solution and decrement left before recursive call .
When # right parentheses is greater than 0 and # right parentheses is less than left, add ")" to solution and decrement right before recursive call.


Iterative method Unknown :(

Non Overlapping Parentheses
----------------------------
Given a set of digits, generate all possible non overlapping parantheses amongst the digits in the set.

Recursive method (Not scalable)
Output is divided into prefix and postfix strings. The prefix strings passed as arguments are perfectly constructed. The recursive module works on building prefix and generating postfix strings.
Complexity O(2^(n-1))
Invariant : Postfix string should have atleast 1 digit.
Print prefix with postfix digits enclosed within parantheses. Append digits (in postfix string) enclosed within parantheses to prefix string till there exists just a single digit on the postfix. Call recursive module for every prefix and postfix generation.

Count and Say Sequence
-----------------------
This sequence blows up very quickly, do not use any native datatype for solving this puzzle. As we just require the previous value to generate the next value, using strings is ideal to solve this puzzle.

There exists two variations for this problem : 
1. Generate the sequence upto n terms 
2. Given  a starting value, generate the nth term value.

Recursive method (Not scalable)

Iterative method (Scalable until program's VM limitations)
Complexity(pn, where p is the pth term of the sequence at which the program stops and n is the maximum length of the string generated)
Datatypes : string and vector to parrse the previous string.
Parse the previous string and store the digits on the vector.
If vector is not empty.
	Initialize variables val to be the value of first digit in vector and count variable to be 1
	Iterate i from 0 through size of the vector
		If value at vector[i] equals val
			Increment count
		else
			Add count to next string
			Add val to next string
			val = vector[i]
			count=1
Edge cases for seed value being null, vector being null, generating n term sequence or the nth term are very trivial.

Reversing bits in a bitmap 
-----------------------------
The following methods assume that the bitmaps belong to integer datatype.
We can make life easier by storing the bitmap on a vector, which increases space complexity.
i. Simple Method to reverse all bits in a bitmap
Time Complexity - O(logN)
Space Complexity - O(1)
Remember (num & (1 << i)) where i ranges from 0th to last bit will reveal whether a bit is set on a value stored inside a native datatype.
If a bit is set in the ith position in the input then set the bit on the output at (# of bits - 1) - i
ii. Reversing every # bits in a bitmap
Time Complexity - O(2*logN) which is O(logN)
Space Complexity - O(1)
Create a helper function which can reverse every # bits stored in an integer datatype variable. Have a main for loop which iterates from 0th to last bit; fill up a temp variable that contains the relevant bitmap pertaining to # bits. When we fill up the relevant bitmap, update the output with the reverse of it. Watchout for corner case where, the last segment # bits might not have been updated on the output. Initialize your index variables and populate the output containing the last segment.

All possible paranthesis to evaluate expression
------------------------------------------------
This is eerily similar to Catalan number sequence problems like parantheses, Dyck's words, etc.
Complexity : Brute force O(n * (C(2n,n) - C(2n, n+1)))
DP solution exists. Complexity could be n!

Least Recently Used Cache
---------------------------
We need to define a class for LRU with capacity, list of key/value stores and a hashmap with key and iterator to the key/value store. Get operation involves hashmap lookup, if successful it is followed by moving of the key/value store to the front of the list. Set operation involves checking whether key already exists to replace the old value with new value, moving the new key/value store to the front of the list and checking whether capacity of the LRU cache has been reached; if so, we erase the last key/value store in the list and its corresponding entry in hashmap. The latter operation of deleting entry in hashmap necessiates the need to store key/value store in the list instead of just values.
Lookups/Get O(1)
Insertion/Set O(1)
Space O(N)
This solution is very much scalable.

Permutation Generator
-----------------------
The maximum number of permutations that can be generated for a string of size n is n!. Work done to construct a string is n, total work done is n*n!. We attempt to generate next permutation in lexicograhic order on a string containing "no duplicates", using the previous result. The algorithm moves from right to left. To be consistent and terminate properly, we should construct the first output/generation to be in ascending order. For the subsequent generations, the procedure is as follows :
1.  Moving from right to left, find the position where the first decrement happens ie (*pos < *(pos+1)); 
1.1 If pos is at the start of the string. No more permutation is possible. Return null result.
2. Moving from right to left, find the index of the element which is > pos.
3. Swap pos and next biggest element.
4. Reverse the rest of the suffix from pos+1
For string with no duplicates, the complexity is O(n*n!), as we can
afford to reverse the suffix blindly.
Note : This method will genrate an infinite loop if we have duplicates on the base string !

Brute force backtracking recursive method exists whose complexity is O(n*n!)
which is not scalable and requires addtional set datastructure to filter
duplicate permutations when the string is known to contain duplicates.

permutation(s, l, r)
	if (l==r) {
		if sol does not contain s
			sol(s)
	} else {
		for (i=l; i<=r; i++) {
			swap(s+l, s+i)
			permutation(s, l+1, r)
			swap(s+l, s+i) // Backtracking
		}
	}

For string with duplicates, the complexity to generate all distinct
permutations is O(nlogn*n!). Note that we have to sort the suffix
containing duplicates after swap, to produce all distinct permutations.

Here is a an example to show the need to sort the suffix
Base string : 1,1,3,5,5,5
-> Swapping decrement and next biggest element
*1,1,5,3,5,5
Now reversing the suffix (3,5,5) would cause us produce (skipping few permutations) 
1,1,5,5,5,3
And then onwards producing permutations that can never lead to those skipped like
1,3,1,5,5,5

Instead of reversing the suffix, had we sorted it
We would not have missed generating
1,1,5,3,5,5
and
1,1,5,5,3,5
before producing
1,1,5,5,5,3 and
1,3,1,5,5,5

Both approaches require base string to be sorted to produce lexicographically
ordered generations.

Finding kth smallest element in an union of two sorted arrays
--------------------------------------------------------------
Brute force method is merge sort the arrays(N,M) up until the kth element gets produced which will take O(k). When k = N+M, then complexity becomes O(N+M)
We can use a divide and conquer method to get the kth smallest element in the union in O(log(N+M)) time

Terminating conditions.
if (sizeA == 0) {
	return b[k];
} else if (sizeB == 0) {
	return a[k];
}


Iterators i and j
i and j can be anything even i = sizeA/2
we can chose weights of array sizes to get values of i, j
For example  i = (int)(((double)sizeA / (sizeA + sizeB)) * (k-1));
             j = k-1-i		
i+j = k-1 is the invariant maintained

a[-1] && b[-1] are -INFINITY and a[sizeA] and b[sizeB] are +INFINITY
to maintain our invariant

        if (bj_1 <= ai && ai <= bj)
                return ai;
        else if (ai_1 <= bj && bj <= ai)
                return bj;

        if (ai <= bj)
                // exclude ai and below portion
                // exclude bj and above portion
                return findKthElement(a+i+1, b, sizeA-i-1, j, k-i-1);
        else
                // exclude ai and above portion
                // exclude bj and below portion
                return findKthElement(a, b+j+1, i, sizeB-j-1, k-j-1);

We can also find the median of an union depending upon the size ul of the union.


int ul = sizeA + sizeB;

        // When the union length is odd, the median is position : ul/2 + 1 , summarized by (ul + 1) >> 1
if (ul & 1)
	return findKthElement(a, b, sizeA, sizeB, ((ul + 1) >> 1));
else
        // When the union length is even, the median is calculated using average of values at ul/2 and (ul/2 + 1)
return (
	(findKthElement(a, b, sizeA, sizeB, ((ul + 1) >> 1)) +
	findKthElement(a, b, sizeA, sizeB, ((ul + 2) >> 1)))
	/
	2.0);