Search in Rotated Sorted Array

Suppose a sorted array is rotated at some pivot unknown to you beforehand.

(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

[Analysis]

At first I thought of using binary search to find the reset index (the 0 in the above example) first, and then use a binary search on the appropriate section. Here is the code of this implementation. The complexity is still O(logN) as this is basically two binary search. The bSearchIndex function returns the reset index, 0 if not rotated and it should never return -1.

class Solution {
    int bSearchIndex(int A[], int n){
        int start = 0;
        int end = n-1;

        while (start <= end) {
            int mid = start + (end-start)/2;
            if (A[mid] > A[end]) {
                start = mid+1;
            } else if (A[mid] < A[end]) {
                end = mid;
            } else {
                return mid;
            }
        }

        return -1;
    }

    int bSearchTarget(int A[], int n, int resetPoint, int target) {
        int start = (target >= A[resetPoint] && target <= A[n-1]) ? resetPoint : 0;
        int end = start == 0 ? resetPoint-1 : n-1;

        if (resetPoint == 0){
            start = 0;
            end = n-1;
        }

        while (start <= end) {
            int mid = start + (end - start)/2;
            if (A[mid] > target)
                end = mid-1;
            else if (A[mid] < target) {
                start = mid+1;
            } else {
                return mid;
            }
        }
        return -1;
    }

public:

    int search(int A[], int n, int target) {
        vector nums;

        int resetIndex = bSearchIndex(A, n);
        return bSearchTarget(A, n, resetIndex, target);
    }
};

However, we don’t necessarily need to know the reset point as pointed out here since we can always deduce on which side resides the target based on the comparison of A[mid] and A[start]. The code is reproduced below.

int rotated_binary_search(int A[], int N, int key) {
  int L = 0;
  int R = N - 1;

  while (L <= R) {
    // Avoid overflow, same as M=(L+R)/2
    int M = L + ((R - L) / 2);
    if (A[M] == key) return M;

    // the bottom half is sorted
    if (A[L] <= A[M]) {
      if (A[L] <= key && key < A[M])
        R = M - 1;
      else
        L = M + 1;
    }
    // the upper half is sorted
    else {
      if (A[M] < key && key <= A[R])
        L = M + 1;
      else
        R = M - 1;
    }
  }
  return -1;
}

The (A[L] <= A[M]) gives us enough information to know which half of the array is sorted, and if left side is sorted, we can compare key with the upper and lower bound of left side to check if target falls in left side, otherwise, it must fall in right half or doesn’t exist. The function return -1 if L>R.

This is also log(N) since it’s a modified version of binary search. It’s not asymptotically faster but absolutely much easier to write. Though my original version gave me quite a good exercise on writing binary search. 😛

Simplify Path

Given an absolute path for a file (Unix-style), simplify it.

For example,
path = "/home/", => "/home"
path = "/a/./b/../../c/", => "/c"

Corner Cases:

• Did you consider the case where path = "/../"?
  In this case, you should return "/".
• Another corner case is the path might contain multiple slashes '/' together, such as "/home//foo/".
  In this case, you should ignore redundant slashes and return "/home/foo".

[Analysis]

The idea is straightforward if ever you think of a stack: pop if we have “..”, nothing if we have “.”, push otherwise.

The interesting part is how to split in c++. There are various ways to do it and the most interesting and most reusable way is to create a separate function to handle this task (I’m jealous of Python at this point :P). It’s a tiny bit slower since we need to go through the path twice, but we are still in O(n) and the gain in reusability wins in my book. Credit to Stackoverflow for the split solution.

vector split(const string &s, char delim) {
    vector elems;
    stringstream ss(s);
    string item;
    // getLine stops at the next delim and put everything before that into item.
    while (getline(ss, item, delim)) {
        elems.push_back(item);
    }
    return elems;
}

string simplifyPath(string path) {
    stack directories;

    vector path_v = split(path, '/');

    string simplePath;

    for (auto s : path_v) {
        if (s.empty()) continue;
        if (s == ".." && !directories.empty())
            directories.pop();
        if (s!= ".." && s != ".")
            directories.push(s);
    }

    while (!directories.empty()){
        simplePath = "/"+directories.top() + simplePath;
        directories.pop();
    }

    if (simplePath.empty())
        simplePath += "/";

    return simplePath;
}

3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

For example, given array S = {-1 0 1 2 -1 -4}, A solution set is: (-1, 0, 1) (-1, -1, 2)

[Analysis]

The most naive approach would be . Note that the sum is 0, if we sort the array at the beginning, we can save a lot of useless check.

There are several optimizations to make though, more details commented in the code.

vector<vector<int> > threeSum(vector<int> &num) {
    vector<vector<int> > res;
    
    if (num.size() < 3)
        return res;
        
    sort(num.begin(), num.end());
    
    for (int i=0; i<num.size()-2; ++i) {
        // there is no need to go further if num[i] doesn't change. 
        // Suppose that we've found a new valid triplet, 
        // it must be a duplicate because previous start and end are already included with this num[i]
        // Also, this gurantee that if num[i] has increased, 
        // this won't be a duplicate, since we know that num[start] and num[end] are both greater than num[i]
        if (i>0 && num[i] == num[i-1]) continue;
        // we know that num[i] <= num[start] <= num[end], 
        // if num[i] > 0 than there is no hope to find a valid triplet.
        if (num[i] > 0) break;
        
        int start = i+1, end = num.size()-1;
        
        while (start < end) {
            int s = num[start]+num[end]+num[i];
            if(start>i+1 && num[start] == num[start-1]) {
                start++;
                continue; // Skip the same num[j] here.
            }
            
            if (s > 0) {
                end--;
            } else if (s < 0){
                start++;
            } else {
                // something new since num[i] has increased
                vector<int> r = {num[i], num[start], num[end]};
                res.push_back(r);
                start++;
                end--;
            }
        }
    }
    
    return res;
}

Longest Consecutive Sequence

Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

For example,
Given [100, 4, 200, 1, 3, 2],
The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

Your algorithm should run in O(n) complexity.

[Analysis]

In O(n) we can’t do a sort. Given O(n), what we can do is to scan through the array. Note that we also need to retain elements which are not sorted and thus not stored in order. We need to retrieve elements in order and it must be a O(1) operation to retrieve the “next” and the “previous” element of a given one. What comes to mind? Hashmap!

int longestConsecutive(vector<int> &num) {
        if (num.empty())
            return 0;
        unordered_set<int> hm;

        for (int i=0; i<num.size(); ++i) {
            hm.emplace(num[i]);
        }

        int max = 0;

        for (int e : num) {
            int c = 1;
            int left = e-1, right = e+1;

            while (hm.find(left)!=hm.end()) {
                c++;
                hm.erase(left);
                left--;
            }

            while (hm.find(right)!=hm.end()) {
                c++;
                hm.erase(right);
                right++;
            }

            max = std::max(c, max);
        }

        return max;
    }

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

[Analysis]

I’ve started out with an attempt to solve this problem in O(n), turns out, that would be way too complicated to handle special cases…

Here is what I’ve tried: initialize a vector of int which stores the longest palindrome found ending at index i. That is, “abacaba” would give me [1,1,3,1,3,5,7], and I just need to scan through the whole array and get the max of the whole array. This seems to be a viable solution, because a sequence of char [start, end] is a palindrome, if and only if [start+1, end-1] is also one. However, considering the case where we have consecutive duplicated characters like “cccccc”, this can become much more complicated to handle.

A straightforward solution is to scan through the whole string, and try to develop a longest palindrome on its left side and right side. The key though, is to recognize that there are only two cases for each character, namely left and right side both starting from index i, or left = i-1 and right = i+1. The time complexity is , acceptable in our case given the assumption that the maximum length of S is 1000.

class Solution {
    string developFromCenter(const string &s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--; right++;
        }

        return s.substr(left+1, right-left-1);
    }

public:
    string longestPalindrome(string s) {
        string res;
        if (s.empty())
            return res;

        for (int i=0; i<s.length(); ++i) {
            string s1 = developFromCenter(s, i, i);
            if (s1.length() > res.length())
                res = s1;

            string s2 = developFromCenter(s, i, i+1);
            if (s2.length() > res.length())
                res = s2;
        }

        return res;
    }
};