Tuesday, April 21, 2015

LeetCode OJ - Median of Two Sorted Arrays

Problem:

Solution:

The requirement on logarithmic run time hint on binary search. Indeed it is. Let's first generalize the problem to finding the kth element first, we are given two sorted array, and need to find the kth element in the merged array.

It is easier to also assume the elements are distinct, to do so, we imagine the two arrays are concatenated and therefore we can associate a unique index $i$ to each element, and we also imagine each element is modified as $A[i] = A[i] + \epsilon i$ with sufficiently small $\epsilon$, that allow us to think of each element as distinct.

Without a better choice, let's consider splitting the arrays by half. The left array becomes $[A, p, B]$ where $A$ is a set of number smaller than $p$, and $B$ is a set of element greater than $p$. Similarly, the right hand side got split into $[C, q, D]$.

Because every element in the array is now unique, only two possibilities can happen, either $p > q$ or $p < q$. For brevity let's look at only the case $p < q$, the other case is similar.

We know $A$ is smaller than $p$, and $p$ is smaller than $q$, so we know $A$ is smaller than $q$. We also know $C$ is smaller than $q$.

On the other hand, we know $D$ is greater than $q$, and know $q$ is greater than $p$, so we know $D$ is greater than $p$. We also know $D$ is greater than $p$.

As a summary, $A, p, C$ are all less than $q$. $B, q, D$ are all greater than $p$.

Now it is the key, either $A, p, C$ has at least $k$ element, or $B, q, D$ has at least $n - k$ element, so we reduced the problem, the rest is trivial.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/median-of-two-sorted-arrays/

#include "LEET_MEDIAN_OF_TWO_SORTED_ARRAYS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_MEDIAN_OF_TWO_SORTED_ARRAYS
{
class Solution
{
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2)
{
int size1 = nums1.size();
int size2 = nums2.size();
int size = size1 + size2;
int mid = size / 2;
if (size % 2 == 0)
{
// a[10] => (a[4] + a[5]) * 0.5
return (select(nums1, nums2, 0, size1, 0, size2, mid - 1) + select(nums1, nums2, 0, size1, 0, size2, mid)) * 0.5;
}
else
{
// a[9] => a[4]
return select(nums1, nums2, 0, size1, 0, size2, mid);
}
}
private:
int select(vector<int>& nums1, vector<int>& nums2, int s1, int e1, int s2, int e2, int k)
{
int size1 = e1 - s1;
int size2 = e2 - s2;
int size = size1 + size2;
if (size1 == 0)
{
return nums2[s2 + k];
}
else if (size2 == 0)
{
return nums1[s1 + k];
}
else
{
// First, all elements n[i] = n[i] + epsilon * i with sufficiently small epsilon, which means all elements are unique (i measured from the two vectors concatenated)
int probe1 = size1 / 2; // To be determined
int probe2 = size2 / 2; // To be determined
int probe1_value = nums1[s1 + probe1];
int probe2_value = nums2[s2 + probe2];

// Denote all the numbers smaller than probe1 in nums1 be the set A with size a
// Denote all the numbers greater than probe1 in nums1 be the set B with size b
// Denote all the numbers smaller than probe2 in nums2 be the set C with size c
// Denote all the numbers greater than probe2 in nums2 be the set D with size d

int a = probe1;
int b = size1 - probe1 - 1;
int c = probe2;
int d = size2 - probe2 - 1;

// Just an algebraic identity, we have
// a + b + c + d = size1 + size2 - 2
//               = size - 2
//     a + c + 1 = size - b - d - 1

if (probe1_value <= probe2_value) // Note the assumption above, it is the same as saying probe1_value epsilon modified is less than as probe2_value
{
if (a + c + 1 >= k + 1)
{
// The number of elements smaller than probe2_value is at least a + c + 1
// so we can safely discard any values known to be larger than or equal to probe2_value
return select(nums1, nums2, s1, e1, s2, s2 + probe2, k);
}
else if (a + c + 1 <= k)
{
// The number of elements greater than probe1_value is at least b + d + 1
// The number of elements smaller than probe1_value is at most size - b - d - 1 = a + c + 1
// so we can safely discard any values known to be smaller than probe1_value
return select(nums1, nums2, s1 + probe1 + 1, e1, s2, e2, k - probe1 - 1);
}
}
else if (probe1_value > probe2_value)
{
if (a + c + 1 >= k + 1)
{
// The number of elements smaller than probe1_value is at least a + c + 1
// so we can safely discard any values known to be larger than or equal to probe1_value
return select(nums1, nums2, s1, s1 + probe1, s2, e2, k);
}
else if (a + c + 1 <= k)
{
// The number of elements greater than probe2_value is at least b + d + 1
// The number of elements smaller than probe2_value is at most size - b - d - 1 = a + c + 1
// so we can safely discard any values known to be smaller than probe2_value
return select(nums1, nums2, s1, e1, s2 + probe2 + 1, e2, k - probe2 - 1);
}
}

return 0;
}
}
};
};

using namespace _LEET_MEDIAN_OF_TWO_SORTED_ARRAYS;

int LEET_MEDIAN_OF_TWO_SORTED_ARRAYS()
{
Solution solution;
// int nums1[] = { };
int nums2[] = { 2, 3 };
vector<int> nums1v;
// vector<int> nums1v(nums1, nums1 + sizeof(nums1) / sizeof(nums1[0]));
vector<int> nums2v(nums2, nums2 + sizeof(nums2) / sizeof(nums2[0]));
cout << solution.findMedianSortedArrays(nums1v, nums2v) << endl;
return 0;
}

LeetCode OJ - Largest Number

Problem:

Solution:

Apparently we wanted to use sorting, but how do we know if one string A should goes before string B?

First consider the case when A is not a prefix of B and B is not a prefix of A, this case is easy. Just do lexicographical order for these two strings. If A is lexicographically ordered after B, then A should goes before B.

An example would be 57 should order before 55, or 444. This is obvious.

Things become tricky if A is a prefix of B. Now it is possible both ways.

Let say A is 12, and B is 123, we have B should goes before A case, the answer is 12312.
Let say A is 12, and B is 121, we have A should goes before B case, the answer is 12121

How should we reconcile this? Consider a special case 3 and 34, we can tell immediately that 34 should goes before 3 because 4 is before 3.

Denote the string B be the concatenation of AB' - it looks like we can tell if A or B should goes first by comparing A and B' - this is the key insight!

Suppose B' should goes before A, then AB'A is better than AAB', so AB' should goes before A.
Suppose A should goes before B', then AAB' is better than AB'A, so A should goes before AB'.

The only case that we cannot tell is when the strings are identical. That correspond to the case that the strings are in fact cannot be compared. Interesting scenario such as 1212 cannot be ordered with 121212, in that case, just pick an arbitrary one will work.

With that, we conclude the exercise with the simple code as follow.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/largest-number/

#include "LEET_LARGEST_NUMBER.h"
#include <list>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

namespace _LEET_LARGEST_NUMBER
{
bool isBefore(string a, string b)
{
for (unsigned int i = 0; i < a.length() && i < b.length(); i++)
{
if (a[i] < b[i])
{
return false;
}
else if (a[i] > b[i])
{
return true;
}
}

if (a.length() == b.length())
{
// True or false doesn't really matter here, they are the same
return false;
}
else if (a.length() > b.length())
{
return isBefore(a.substr(b.length(), a.length() - b.length()), b);
}
else
{
return isBefore(a, b.substr(a.length(), b.length() - a.length()));
}
}

class Solution
{
public:
string largestNumber(vector<int> &num)
{
int n = num.size();
vector<string> nums;
vector<bool> free;

for (int i = 0; i < n; i++)
{
stringstream iss;
iss << num[i];
nums.push_back(iss.str());
free.push_back(true);
}

sort(nums.begin(), nums.end(), isBefore);

stringstream oss;
for (int i = 0; i < n; i++)
{
oss << nums[i];
}

string s = oss.str();

if (s[0] == '0')
{
return "0";
}
else
{
return s;
}
}
};
};

using namespace _LEET_LARGEST_NUMBER;

int LEET_LARGEST_NUMBER()
{
Solution solution;
int data[] = {3, 30, 34, 5, 9};
vector<int> input (data, data + sizeof(data) / sizeof(data[0]) );
cout << solution.largestNumber(input) << endl;
return 0;
}

Friday, April 10, 2015

LeetCode OJ - Binary Tree Preorder Traversal

Problem:

Solution:

A pretty standard solution for pre-order traversal.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-tree-inorder-traversal/

#include "LEET_BINARY_TREE_PREORDER_TRAVERSAL.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

namespace _LEET_BINARY_TREE_PREORDER_TRAVERSAL
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
vector<int> preorderTraversal(TreeNode *root)
{
vector<int> result;
this->preorderTraversal(root, result);
return result;
}
private:
void preorderTraversal(TreeNode *root, vector<int>& result)
{
if (root != NULL)
{
result.push_back(root->val);
this->preorderTraversal(root->left, result);
this->preorderTraversal(root->right, result);
}
}
};
}

using namespace _LEET_BINARY_TREE_PREORDER_TRAVERSAL;

int LEET_BINARY_TREE_PREORDER_TRAVERSAL()
{
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
a.left = NULL;    a.right = &c;
b.left = NULL;    b.right = NULL;
c.left = &b;      c.right = NULL;
Solution solution;
vector<int> result = solution.preorderTraversal(&a);
for (vector<int>::iterator ri = result.begin(); ri != result.end(); ri++)
{
cout << *ri << endl;
}

return 0;
}

LeetCode OJ - Binary Tree Inorder Traversal

Problem:

Solution:

A pretty standard solution for in-order traversal.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/binary-tree-inorder-traversal/

#include "LEET_BINARY_TREE_INORDER_TRAVERSAL.h"

#include <vector>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>

using namespace std;

namespace _LEET_BINARY_TREE_INORDER_TRAVERSAL
{
struct TreeNode
{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution
{
public:
vector<int> inorderTraversal(TreeNode *root)
{
vector<int> result;
this->inorderTraversal(root, result);
return result;
}
private:
void inorderTraversal(TreeNode *root, vector<int>& result)
{
if (root != NULL)
{
this->inorderTraversal(root->left, result);
result.push_back(root->val);
this->inorderTraversal(root->right, result);
}
}
};
}

using namespace _LEET_BINARY_TREE_INORDER_TRAVERSAL;

int LEET_BINARY_TREE_INORDER_TRAVERSAL()
{
TreeNode a(1);
TreeNode b(2);
TreeNode c(3);
a.left = NULL;    a.right = &c;
b.left = NULL;    b.right = NULL;
c.left = &b;      c.right = NULL;
Solution solution;
vector<int> result = solution.inorderTraversal(&a);
for (vector<int>::iterator ri = result.begin(); ri != result.end(); ri++)
{
cout << *ri << endl;
}

return 0;
}

LeetCode OJ - Climbing Stairs

Problem:

Solution:

Another classic problem in dynamic programming. The problem manifest itself in many different flavors. Counting the number of paths, counting the number of ways to reach top, counting the number of ways of change coin, ... etc.

The key idea is that to to reach n steps is to either make a step of 1 and count the number of steps to reach the top, or make a step of 2 and count the number of steps to reach the top.

So the recurrence is $T(n) = T(n - 1) + T(n - 2)$, and therefore the solution is obvious! Fibonacci numbers!

I am aware of the logarithmic solution for Fibonacci numbers. But notice the required return type is int, so there is no need, the recursive formulation introduce more overhead than speed.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/climbing-stairs/

#include "LEET_CLIMBING_STAIRS.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_CLIMBING_STAIRS
{
class Solution
{
public:
int climbStairs(int n)
{
if (n == 0 || n == 1)
{
return 1;
}
else
{
int a = 1;
int b = 1;
int c = 0;
for (int i = 2; i <= n; i++)
{
c = a + b;
a = b;
b = c;
}
return c;
}
}
};
};

using namespace _LEET_CLIMBING_STAIRS;

int LEET_CLIMBING_STAIRS()
{
Solution solution;
for (int i = 1; i <= 10; i++)
{
cout << solution.climbStairs(i) << endl;
}
return 0;
}

LeetCode OJ - Populating Next Right Pointers in Each Node

Problem:

Solution:

The real challenge here is constant space, so recursive solution is ruled out. Our best chance is to do a level order traversal. The key problem is how to do that, and the key idea to achieve this is to leverage the next pointer we just build in the last layer!

Code:

#include "stdafx.h"

// https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

#include "LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE
{
{
};

class Solution
{
public:
{
if (root == NULL)
{
return;
}

root->next = NULL;

while (nextLayerStart != NULL)
{
nextLayerStart = nextLayerStart->left;
if (nextLayerStart == NULL)
{
break;
}

while (currentLayerCursor != NULL)
{
currentLayerCursor->left->next = currentLayerCursor->right;
if (currentLayerCursor->next == NULL)
{
currentLayerCursor->right->next = NULL;
}
else
{
currentLayerCursor->right->next = currentLayerCursor->next->left;
}

currentLayerCursor = currentLayerCursor->next;
}
}
}
};
};

using namespace _LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE;

int LEET_POPULATING_NEXT_RIGHT_POINTERS_IN_EACH_NODE()
{
a.left = &b;
a.right = &c;
b.left = &d;
b.right = &e;
c.left = &f;
c.right = &g;
d.left = NULL;
d.right = NULL;
e.left = NULL;
e.right = NULL;
f.left = NULL;
f.right = NULL;
g.left = NULL;
g.right = NULL;
Solution solution;
solution.connect(&a);
cout << ((a.next == NULL) ? "Yes" : "No") << endl;
cout << ((b.next == &c  ) ? "Yes" : "No") << endl;
cout << ((c.next == NULL) ? "Yes" : "No") << endl;
cout << ((d.next == &e  ) ? "Yes" : "No") << endl;
cout << ((e.next == &f  ) ? "Yes" : "No") << endl;
cout << ((f.next == &g  ) ? "Yes" : "No") << endl;
cout << ((g.next == NULL) ? "Yes" : "No") << endl;
return 0;
}

LeetCode OJ - Single Number II

Problem:

Solution:

We already solved Single Number, so all we have to do is to generalize it. Considering exclusive-or as addition modulo 2, all we really need is addition modulo 3, and do that per digit.

So the first step is to extend the number into a base 3 number instead of base 2. As binary representation, we will need one more bit per bit, so I used an 64-bit integer, the most significant 32 bits are the most significant bit for the digit. So it is represented like this:

Base 3 representation: 2 0 1 0
Binary representation 10 00 01 00
Represented in code: 1 0 0 0 0 0 1 0

The cool thing about this representation is that we can change a number into its base 3 version simply by adding a bunch of 0 before it, and obviously, we can extract the original number by just taking the lowest 32 bits.

So we simply extract each digit, add it, modulo 3, and put it back, nothing special about that.

Last but not least, if somehow the array has 3n + 2 elements, we need to divide the number by 2. It can be easily done by multiplying it with the multiplicative inverse of 2, which is 2 again because (2 x 2 = 4 = 1 mod 3).

Be careful with signed integer, we need to explicitly cast it to unsigned to avoid sign extension.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/single-number-ii/

#include "LEET_SINGLE_NUMBER_II.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_SINGLE_NUMBER_II
{
typedef long long int64;

class Solution
{
public:
int singleNumber(int A[], int n)
{
int64 accumulator = 0;
for (int i = 0; i < n; i++)
{
int64 hi_mask = (int64)1 << 32;
for (int d = 0; d < 32; d++)
{
int64 ac_lo = accumulator & lo_mask;
int64 ac_hi = accumulator & hi_mask;
int64 ar_lo = (unsigned int)A[i] & lo_mask;
int64 ar_hi = (unsigned int)A[i] & hi_mask;

int ac_digit = ((ac_hi == 0) ? 0 : 2) + ((ac_lo == 0) ? 0 : 1);
int ar_digit = ((ar_hi == 0) ? 0 : 2) + ((ar_lo == 0) ? 0 : 1);

int sum = (ac_digit + ar_digit) % 3;

switch (sum)
{
case 0:
// The digit is already reset
break;
case 1:
break;
case 2:
break;
}

}
}

if (n % 3 == 2)
{
int64 hi_mask = (int64)1 << 32;
for (int d = 0; d < 32; d++)
{
int64 ac_lo = accumulator & lo_mask;
int64 ac_hi = accumulator & hi_mask;

int ac_digit = ((ac_hi == 0) ? 0 : 2) + ((ac_lo == 0) ? 0 : 1);

int quoient = (ac_digit * 2) % 3;

switch (quoient)
{
case 0:
// The digit is already reset
break;
case 1:
break;
case 2:
break;
}

}
}

return (accumulator << 32) >> 32;
}
};
};

using namespace _LEET_SINGLE_NUMBER_II;

int LEET_SINGLE_NUMBER_II()
{
int A[] = { -2, -2, 1, 1, -3, 1, -3, -3, -4, -2 };
Solution solution;
cout << solution.singleNumber(A, 10) << endl;
return 0;
}