Shuffle an Array

Question:
Given an input array, shuffle it and output a randomized sequence.

Analysis:
The array can actually be of any type, not necessary integer or number. One special example is to shuffle a deck of cards. That happens to be of integer type.

Variations:
There may be different variations of this similar problem. I hope to summarize all the cases here and would like to go through each with some implementation.

1. Randomize an array of n elements
2. Randomly select m elements out of an array of n elements
3. Randomly select m elements out of a stream of n elements (n is known before hand)
4. Randomly select m elements out of a stream of elements (not sure how many elements there are until stopping reading)

This blog talks about Case 1. The code is not hard but there are some tricks. It's better to select from the end of array and that will help control the number of elements remained. Also, the code will be cleaner.


The mathematical proof would be trickier and it's good to have some combinatorics. The probability of any output sequence will be \[\frac{1}{n!}\]

Are 2 Strings Anagrams or Not?

Problem:
Given 2 strings, determine if they are anagrams. Anagram means the 2 strings contain exactly the same characters and number of appearances. In other words, we can do a permutation to get the other string from one string.

Solution 1:
Sort the 2 strings first, then if they are anagrams, the sorted strings must be identical. Otherwise, they are not.

In C++, we may use the library function sort in the header < algorithm >. This function is comparison based and the average time complexity is \(O(n\log n)\).


Solution 2:
Since the character values are always in a fixed range, and in this case, counting sort is good approach. In this way, we may obtain \(O(n)\) time complexity and \(O(n)\) space complexity.


Solution 3:
Similar to the idea of counting sort, we don't actually sort the strings. All we need is the counts of characters appearing in the strings. If the counts for each character are equal, then the 2 strings are anagram. This solution also exhibit \(O(n)\) time complexity, but \(O(1)\) space complexity.


Solution 4:
Even more, we can just count the characters for one string, and make judgement while scanning the other. This approach also has \(O(n)\) time complexity and \(O(1)\) space complexity.
There is a bug in Solution 4. What if s1 is longer and contains all characters in s2? For example, s1="abcd", s2="ab".

Two possible solutions for this:

1. Add a length check at the beginning. Two strings must be of the same length to be anagram.
2. Add another round of check on the count array after scanning the second string. All entries should be 0.

Maximize Payoff by Greedy Reordering

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 384, Problem 16.2-7

Problem:
Suppose you are given two sets \(A\) and \(B\), each containing \(n\) positive integers. You can choose to reorder each set however you like. After reordering, let \(a_i\) be the \(i\)th element of set \(A\), and let \(b_i\) be the \(i\)th element of set \(B\). You then receive a payoff of \(\prod_{i=1}^{n}{a_i^{b_i}}\). Given an algorithm that will maximize your payoff. Prove that your algorithm maximizes the payoff, and state its running time.

Solution:
Greedy Algorithm: Let the set \(\{a_i\}\) be sorted so that \(a_1 \ge a_2 \ge \ldots \ge a_n\) and set \(\{b_i\}\) be sorted so that \(b_1 \ge b_2 \ge \ldots \ge b_n\). Pair \(a_i\) with \(b_i\). This is the required solution.

Complexity:
If the two sets \(A\) and \(B\) are already sorted, the time complexity is \(O(n)\).
If the sets are not sorted, then sort them first and the time complexity is \(O(n\log n)\).

Proof:
Suppose the optimal payoff is not produced from the above solution. Let \(S\) be the optimal solution, in which \(a_1\) is paired with \(b_p\) and \(a_q\) is paired with \(b_1\). Note that \(a_1 \gt a_q\) and \(b_1 \gt b_p\).

Consider another solution \(S'\) in which \(a_1\) is paired with \(b_1\), \(a_q\) is paired with \(b_p\), and all other pairs are the same as \(S\). Then \[\frac{\text{Payoff}(S)}{\text{Payoff}(S')}=\frac{\prod_{S}\hspace{2 mm} a_i^{b_i}}{\prod_{S'}\hspace{2 mm}a_i^{b_i}}=\frac{(a_1)^{b_p} (a_q)^{b_1}}{(a_1)^{b_1} (a_q)^{b_p}}=(\frac{a_1}{a_q})^{b_p - b_1}\] Since \(a_1 \gt a_q\) and \(b_1 \gt b_p\), then \(\text{Payoff}(S) / \text{Payoff}(S') \lt 1\). This contradicts the assumption that \(S\) is the optimal solution. Therefore \(a_1\) should be paired with \(b_1\). Repeating the argument for remaining elements, we can get the result.

A More Efficient Algorithm for Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length \(n\), find a longest increasing subsequence.
In my previous post, I discussed the dynamic programming approach with time complexity \(O(n^2)\). For this specific problem, we can have a more efficient algorithm which is also based on dynamic programming. Please see Wikipedia for reference.

The algorithm uses only arrays and binary searching. It processes the sequence elements in order, maintaining the longest increasing subsequence found so far. Denote the sequence values as \(X[1]\), \(X[2]\), etc. Then, after processing \(X[i]\), the algorithm will have stored values in two arrays:

\(M[j]\) — stores the position \(k\) of the smallest value \(X[k]\) such that there is an increasing subsequence of length \(j\) ending at \(X[k]\) on the range \(k ≤ i\) (note we have \(j ≤ k ≤ i\) here).

\(P[k]\) — stores the position of the predecessor of \(X[k]\) in the longest increasing subsequence ending at \(X[k]\).

In addition the algorithm stores a variable \(L\) representing the length of the longest increasing subsequence found so far.

Note that, at any point in the algorithm, the sequence \[X[M[1]], X[M[2]], ..., X[M[L]]\] is nondecreasing. For, if there is an increasing subsequence of length \(i\) ending at \(X[M[i]]\), then there is also a subsequence of length \(i-1\) ending at a smaller value: namely the one ending at \(X[P[M[i]]]\). Thus, we may do binary searches in this sequence in logarithmic time.

The algorithm, then, proceeds as follows.

L = 0
for i = 1, 2, ... n:
   binary search for the largest positive j ≤ L 
     such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
   P[i] = M[j]
   if j == L or X[i] < X[M[j+1]]:
      M[j+1] = i
      L = max(L, j+1)

The result of this is the length of the longest sequence in \(L\). The actual longest sequence can be found by backtracking through the \(P\) array: the last item of the longest sequence is in \(X[M[L]]\), the second-to-last item is in \(X[P[M[L]]]\), etc. Thus, the sequence has the form \[..., X[P[P[M[L]]]], X[P[M[L]]], X[M[L]].\]
Because the algorithm performs a single binary search per sequence element, its total time can be expressed using Big \(O\) notation as \(O(n\log n)\).


References:

Wikipedia item: longest increasing subsequence

Related Posts:

\(O(n^2)\) Algorithm for Longest Increasing Subsequence

Longest Increasing Subsequence

Problem:
Given an array of numbers or a string of length \(n\), find a longest increasing subsequence.

Brute-force approach:
Enumerate all possible subsequences and then determine which are increasing and store the longest one. This approach is obviously impractical for large \(n\) and its time complexity is exponential.

Dynamic programming approach:
The longest increasing subsequence of an array \(A\) of length \(n\) can be determined based on that of all the prefix arrays. We need use an auxiliary array \(T[n]\), in which \(T[i]\) stores the length of longest increasing (non-decreasing) subsequence ending at \(A[i]\). Notice that is ending at, i.e., the last element must be \(A[i]\). Meanwhile, the global maximum length is also stored in variable \(L\). The time complexity for this algorithm will be \(O(n^2)\).



Related Posts:

\(O(n\log n)\) Algorithm for Longest Increasing Subsequence

Remove Duplicate Characters

Problem:
Given a string, remove the duplicate characters in the string.

Assumption:
All the characters are from ASCII set and in the range 0~255. Also, the character null character does not appear in the string.

Requirement:
An extra copy of the array is not allowed.

Similar to last post about approaches to deciding unique characters or not, this can be done in place or with an array of fixed size.

Note:
Although C++ algorithm library has unique function, which may seem appropriate for this problem. However, that unique function just removes the consecutive duplicates.

We may also sort the string first if we can remove any duplicates, not necessarily keeping the first one in appearance order. In this way, we may get to time complexity \(O(n\log n)\). Also, this method would destroy the order of unique characters. This solution is not shown in this post.

Solution 1:
For each character in the string and unique, detect all duplicates in the string afterwards. Mark those duplicates and remove them in the end. Suppose the string is given as a char array, otherwise we may need convert a String to StringBuffer, StringBuilder, or CharArray.

Solution 2:
For each character in the string, first determine if it's duplicate. If yes, simply skip it; if not, keep it in the string.

Solution 3:
An extra array of fixed size can be used to record which characters have appeared. This can reduce the time complexity from \(O(n^2)\) to \(O(n)\). Also, we can have boolean array or bitset approaches. Each of them can be applied to the above 2 schemes and we can have 4 different algorithms. Here, I am showing boolean array with Scheme 1 in this solution, and bitset with Scheme 2 for next solution.

Solution 4:
Use bitset with the above Scheme 2 to remove the duplicates.

String Contains All Unique Characters or Not

Problem:
Given a string, determine if this string contains all unique characters.

Assumption:
The characters in this string are from ASCII character set. In other words, the value range is 0~255.

Solution 1:
Directly compare each character in the string with every other character in the string. This approach will take \(O(n^2)\) time and no space.

Solution 2:
If allowed to destroy the string, we may first sort the string using quicksort, and then scan through the string to see if there are 2 adjacent characters are the same. Quicksort will take \(O(n\log n)\) time and \(O(1)\) space. If using mergesort, it will take \(O(n)\) space. In Java, to sort the string, an extra array or StringBuffer is needed.

Solution 3:
Since the characters are in a small range, and we can create an array to record if one certain character has appeared or not. This approach will take \(O(n)\) time and \(O(m)\) space, where \(m\) is the size of character set.

Solution 4:
Similar to Solution 3, but instead of using an array of boolean values, use a set of bits to record the binary values. In Java, \(256/32=8\) int size bits are needed, which can be implemented as an array of 8 integers, and each integer represents 32 characters. In C++, there is a very convenient structure called bitset, which can be beautifully used here.

Notes:
Since the characters are all from the assumed set, and the set size is known. In this case, the maximum length for a string of all unique characters will be the size of the character set. Therefore, for each of the above programs, we may add the following code.

if( s.length() > 256 ) return false;

The Number of Inversions in an Array

Problem:
Let \(A[1...n]\) be an array of \(n\) distinct numbers. If \(i \lt j\) and \(A[i] \gt A[j]\), then the pair \( (i,j) \) is called an inversion of A. Determine the number of inversions given an array of distinct numbers.

Solution 1:
Naive approach. There are \( \frac{n(n-1)}{2} \) number pairs in an array of size \(n\), and check one by one. The time complexity is \(O(n^2)\).

We can have a better solution for this problem, which is proposed as below.

Solution 2:
Divide-and-conquer. This strategy works in similar way to merge-sort, and bears time complexity \(n\log n\).

First Pair Summing to Given Number

Problem:
Given an array of integers, find the first pair whose sum equals the given number.

Example:
Given array [14, 8, 5, 7, 4, 1, 20] and number 12, return (5, 7).

Clarification:
The term "first pair" means the both 2 numbers appear before the latter of any other pair. In above example, the first pair is (5, 7) instead of (8, 4).

Thinking:
I discussed the brute force way to solve this problem (post here). The code is simple and it runs in \(O(n^2)\) time. Why can't we use sorting first? Because it will destroy the appearance order? Do we have a way to keep track of the appearance order?

The answer is YES! We can use an auxiliary array to keep track of the appearance during sorting. After sorting, this array can be used to find the first pair we need. Sorting is always a good approach. At the same time, we should notice that this algorithm is \(O(n\log n)\) in time but \(O(n)\) in space, while the brute-force approach only costs \(O(1)\) space. This is a common trade-off.

In the code below, I assume that we don't know the range of the numbers, so we can only rely on the comparison-based sorting algorithms, which means it's unable to achieve \(O(n)\) complexity in time.


Related Posts:

Brute Force Approach to Solve this Problem

First Pair Summing to Given Number

Problem:
Given an array of integers, find the first pair whose sum equals the given number.

Example:
Given array [14, 8, 5, 7, 4, 1, 20] and number 12, return (5, 7).

Clarification:
The term "first pair" means the both 2 numbers appear before the latter of any other pair. In above example, the first pair is (5, 7) instead of (8, 4).

Thinking:
A typical way to find if there are 2 elements in an array such that their sum is a given number is that sort the array first, and then use an auxiliary array and 2 pointers (or something alike, like array indices), scanning the 2 arrays once. The bottleneck of this approach is sorting, and its complexity is \(O(n\log n)\).

But the problem here is to find the first pair, which increases the difficulty. At a glance, sorting may destroy the order of elements in original array, and if doing so, we'll have no idea which pair is the right one. Following this acknowledgement, we may only use a brute-force approach to check each pair by order. Although an auxiliary array can be made use of, but that will also take \(O(n^2)\) in time, with no real improvement.

Although there IS a better way (post here) to do this problem, this post just shows the brute-force code and it's not so ugly.

Related Posts:

\(O(n\log n)\) Approach to Solve this Problem

Binary Search Heavier Ball

Given a line of balls, of which one is heavier and all others are the same.
Also, given a function called balance, which works on an array and tells whether the front part or back part is heavier.

Problem: find the heavier ball.

Thinking: it is natural to consider binary search approach. Yes, and it is also efficient with \(O(\log n)\) complexity in time. But there are some subtle problems with the function "balance". This function works like a scale and can only tell which side is heavier. If the heavier side has more balls than the other, we don't know whether this is due to the extra ball or due to the heavier ball. Hence, if we want the function "balance" to work well in this problem, extra energy is needed to guarantee that the balls on each side are equal in terms of number.

Assume the prototype of balance function is
int balance(int A[ ], int l, int r, int p);
The array A represents the array of balls to be balanced, where l is the left end of the array, r is the right end of the array, and p is the partition point where l, l+1, ..., p will be seen as the front part, and p+1, p+2, ..., r the back part. The return value can be 1, -1, or 0. 1 means front part is heavier, -1 means back part is heavier, and 0 means front part and back part weight the same.

Based on this, we can have following solution (code):

To solve the original problem, we need call searchHeavier(A,0,n-1) (assuming there are n balls).

The code above was a recursive function. It's easy to convert it to an iterative version (not shown here).

More thinking about this problem:
If we don't know for sure there is a ball heavier than all other balls. In other words, there is at most one ball which is heavier and all other balls are the same. In this case, only one change need be made to above code: is the remaining ball really heavier? The modified code is as below:

Direct Addressing on Huge Array

Source: CLRS, Introduction to Algorithms, 2nd Edition, Page 223, Problem 11.1-4

Problem:
We wish to implement a dictionary by using direct addressing on a huge array. At the start, the array entries may contain garbage, and initializing the entire array is impractical because of its size. Describe a scheme for implementing a direct-address dictionary on a huge array. Each stored object should use O(1) space; the operations SEARCH, INSERT, and DELETE should take O(1) time each; and the initialization of the data structure should take O(1) time.

Hint:
Use an additional stack, whose size is the number of keys actually stored in the dictionary, to help determine whether a given entry in the huge array is valid or not.

Solution:
Simply speaking, given an uninitialized huge array, implement a dictionary.
Besides the huge array, one more array can be used to store the actual objects (or their pointers). Call these 2 arrays H and S, respectively. Initially, the arrays contains no records and define a variable n = 0. For a certain key k, if k already exists in the dictionary, we want to keep this relationship: H[k] = i and S[i] = k (or S[i] points to the object with key k). Therefore, H[ S[i] ] = i and S[ H[k] ] = k should both hold for a valid record.

Now we design the dictionary operations:
Initialize: build an empty stack.
Search: given a key k, test 1 ≤ H[k] ≤ n && S[ H[k] ] == k, if true, found and return S[ H[k] ]; otherwise, not found.
Insert: if key k already exists, replace it; otherwise push k into S, say, S[n+1] ← k and n ← n+1, and update the dictionary by H[k] ← n (already incremented).
Delete: delete the object with key k. First search to make sure the record is in the dictionary. If found, after simply deleting the record, there will be a gap in the entry with index H[k] in array S. Need fill in this gap while maintaining the correct relationship between H and S. This involves the following steps:

• S[ H[k] ] ← S[n]
• H[ S[n] ] ← H[k]
• H[k] ← NULL
• S[n] ← NULL
• n ← n-1

All these operations can be done in time O(1).

References:

http://ripcrixalis.blog.com/2011/02/08/hello-world/

http://www.cs.duke.edu/courses/summer02/cps130/Homeworks/Solutions/H11-solution.pdf