Candy

[Candy]

There are N children standing in a line. Each child is assigned a rating value.

You are giving candies to these children subjected to the following requirements:

  • Each child must have at least one candy.
  • Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

[Analysis]

To solve this problem in O(n) there are several observations to be made.

  1. when we scan through the ratings, there is constraint on the number of candies of i and i-1 when we are in a ascending position (ratings[i-1] < ratings[i]) but there is no constraints if we are not in such a position.
  2. starting with 1 candy for each child, we should only increase the number of candies to be distributed, but never reduce it, otherwise, we would break some constraints previously calculated

The following solution is inspired by this post, with more detailed comments.


class Solution {
public:
    int candy(vector<int> &ratings) {
        vector<int> candies(ratings.size(), 1);
        
        // scanning through the ratings from left to right while 
        // maintaining the rules for all rising positions
        for (int i=1; i<ratings.size(); ++i) {
            if (ratings[i] > ratings[i-1])
                candies[i] = candies[i-1]+1;
        }
        
        int sum = 0;
        // scanning through the ratings from right to left while 
        // maintaining the rules for all rising positions 
        // (descending positions in the first loop)
        for (int i=ratings.size()-2; i>=0; --i) {
            // we only want to increase numbers, not reduce them. 
            // !(candies[i] >= candies[i+1]+1) gurantees that we will only increase it
            // if we increase a number from right to left, we will never break the right policy
            // previously assured left policy will be maintained if we only increase a number
            if (ratings[i] > ratings[i+1] && !(candies[i] >= candies[i+1]+1))
                candies[i] = candies[i+1]+1;
            sum += candies[i+1];
        }
        sum += candies[0];
        
        return sum;
    }
};

Search in Rotated Sorted Array

[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

[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

[3Sum]

Given an array S of n integers, are there elements abc 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 O(n^2). 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

[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

[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 O(n^{2}), 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;
    }
};

Insert Interval

Recently I’m preparing for my very first technical interview so I think it might be a good idea to blog about my thoughts on some of the algorithmic questions here.

Most of the questions are from LeetCode OJ, you can find more questions here.

[Insert Interval]

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

[Analysis]

Let’s call the interval to be inserted newInterval while original intervals are given in a vector<Interval> called intervals.

The definition of Interval is given below:

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */

The basic idea is to scan through the intervals and compare newInterval with the interval being scanned. When we want to insert an interval among others, there are in total three cases:

  1. current interval doesn’t overlap with newInterval and precedes newInterval
  2. current interval doesn’t overlap with newInterval and follows newInterval
  3. the two overlap, in this case, we need to merge the two of them

Now, the key is to understand that newInterval always holds the interval to be added, but we are still not sure if we need a merge or to wait before doing so.

Also, I find it really helpful to deal with simple cases first, and only concentrate on the “need to merge” one at the end.

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
	vector<Interval> res;

	for (int i=0; i<intervals.size(); ++i) {
		if (intervals[i].end < newInterval.start) {
			res.push_back(intervals[i]);
		} else if (intervals[i].start > newInterval.end) {
			res.push_back(newInterval);
			newInterval = intervals[i];
		} else {
			// need a merge
			newInterval.start = min(intervals[i].start, newInterval.start);
			newInterval.end = max(intervals[i].end, newInterval.end);
		}
	}

	res.push_back(newInterval);

	return res;
}

Note that one line 17, we always push_back newInterval, because that’s what is “to be” inserted, so if the newInterval turns out to be the last one, we need to push that as well.