[codeFights] almostIncreasingSequence

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

• For sequence = [1, 3, 2, 1], the output should be
  almostIncreasingSequence(sequence) = false;
  There is no one element in this array that can be removed in order to get a strictly increasing sequence.
• For sequence = [1, 3, 2], the output should be
  almostIncreasingSequence(sequence) = true.
  You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

• [execution time limit] 3 seconds (cs)
• [input] array.integer sequence
  Guaranteed constraints:
  2 ≤ sequence.length ≤ 105,
  -105 ≤ sequence[i] ≤ 105.
• [output] boolean
  Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

So, my first thought was to calculate the longest increasing sequence for `sequence`, but it exceeded the time limit - of course, if the longest input can be 10^5, then O(n^2) algorithm should not work. One intuition is that longest increasing sequence calculates more things than we actually need. Here we can only have one element out of order, and thus decrease the difficulty of calculation.

Another note is that I start to use C# instead of python, for working purpose. My company mainly uses C#, and I want to learn.

bool almostIncreasingSequence(int[] sequence) {
    
    int leftMax = sequence[0];
    int leftMaxIndex = 0;
    int removed = 0;
    
    for(int i=1; i<sequence.Length; i++)
    {
        if(sequence[i]<=leftMax)
        {
            //need to remove leftMax
            if(removed >= 1)
                return false;
            //no items has been removed before
            if(leftMaxIndex > 0)
            {
                if (sequence[i] > sequence[leftMaxIndex-1])
                {
                    leftMax = sequence[i];
                    leftMaxIndex = i;
                }
            }
            else
            {
                leftMaxIndex = i;
                leftMax = sequence[i];
            }
            removed += 1;
        } 
        else
        {
            leftMaxIndex = i;
            leftMax = sequence[i];
        }
    }
    return true;
}

[Leetcode] 334. Increasing Triplet Subsequence

This problem reminds me of the fancy version of longest increasing subsequence problem ($O(n\log n)$ solution).

Let's look at an example array: 1, 2, -1, 1, -2, 3. When we go through the first two element, we are all good. Then, we encounter -1, here we face a decision, should we update the current minimum to -1?

Let's see why we should and why we shouldn't. -1 is a safer move than 1, what if later our solution is -1, 0, 1? Then we definitely want to update it. However, you might say, if we update it to -1, then 2 shouldn't be in our solution anymore, according to the "subsequence" rule.

Well, the answer is YES, but we only update the minimum, keeping the second minimum (which is 2 here).The argument is as following: when we keep the second minimum (call it min2), this means that we only count increasing when the next value is greater than min2. You see, by changing min1 to a smaller value, it doesn't really affect the decision we are going to make about adding an increasing element. However, if we see the next value is smaller than min2 but greater than min1, we then want to update min2.

In this way, we always keep track the safest possible value yet maintain the order we have for now.

In actual implementation, I used a stack instead of min1, min2. It turned out to be much easier to handle. Well, who knows such a seeming simple question took me good two hours to think through - this kind of question is very tricky.

---

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

---

class Solution(object):
    def increasingTriplet(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        if len(nums) < 3: return False
        
        counter = 1
        stack = []
        for i in nums:
            if len(stack) == 0:
                stack.append(i)
            elif i < stack[0]:
                stack[0] = i
            elif len(stack) == 1 and i > stack[0]:
                stack.append(i)
            elif len(stack) == 2 and stack[0] < i < stack[1]:
                stack[1] = i
            elif len(stack) == 2 and i > stack[1]:
                return True
        return False

[Leetcode] 164. Maximum Gap

A really smart solution using pigeon hole principle and bucket sort...

---

Given an unsorted array, find the maximum difference between the successive elements in its sorted form.

Try to solve it in linear time/space.

Return 0 if the array contains less than 2 elements.

You may assume all elements in the array are non-negative integers and fit in the 32-bit signed integer range.

---

class Solution(object):
    def maximumGap(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums: return 0
        min_v, max_v = min(nums), max(nums)
        if min_v == max_v: return 0
        
        buckets = [[] for _ in range(len(nums)+1)]
        for num in nums:
            bkt = (num - min_v) * len(nums) / (max_v - min_v)
            buckets[bkt].append(num)
        
        i = 0
        res = 0
        while i < len(buckets) - 1:
            k = i + 1
            while len(buckets[k]) == 0:
                k = k + 1
            res = max(res, min(buckets[k]) - max(buckets[i]))
            i = k
        return res

[Leetcode] 498. Diagonal Traverse

Well, this problem itself has nothing to note. But I must take a screen shot for record - the first time my program beats 100%... just for fun. Problem wise, it's just a bunch of index tricks - along the diagonal, element matrix[i][j], i + j maintains the same.

---

Given a matrix of M x N elements (M rows, N columns), return all elements of the matrix in diagonal order as shown in the below image.

Example:

Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output:  [1,2,4,7,5,3,6,8,9]
Explanation:

Note:

1. The total number of elements of the given matrix will not exceed 10,000.

---

One thing to note is that the input size says that we can only afford $O(n)$ algorithm.

class Solution(object):
    def findDiagonalOrder(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: List[int]
        """
        if not any(matrix): return []
        m, n = len(matrix), len(matrix[0])
        
        if m == 1: return matrix[0]
        if n == 1: return [matrix[i][0] for i in range(m)]
        
        res = []
        for k in range(m+n):
            if k >= n:
                start = k -n + 1 # row 
            else:
                start = 0
            if k >= m:
                end = m - 1 
            else:
                end = k
            tmp = []
            for i in range(start, end + 1):
                tmp.append(matrix[i][k-i])
            
            if k % 2 == 0:
                res += tmp[::-1]
            else:
                res += tmp
        return res
       

[CodeFights] firstDuplicate

A google problem.. The problem sounds very simple. The tricky part is the time and space constraint.

Note: Write a solution with O(n) time complexity and O(1) additional space complexity, since this is what you would be asked to do during a real interview.

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.

Example

• For a = [2, 3, 3, 1, 5, 2], the output should be
  firstDuplicate(a) = 3.
  There are 2 duplicates: numbers 2 and 3. The second occurrence of 3 has a smaller index than than second occurrence of 2 does, so the answer is 3.
• For a = [2, 4, 3, 5, 1], the output should be
  firstDuplicate(a) = -1.

The key point is that numbers are in the range from 1 to len(a). This reminds me of another leetcode problem: First missing positive.

In FirstMissingPositive, we take advantage of the same condition "numbers are in the range from 1 to len(a)" and treat the original array as a hashmap. Whenever we encounter a out-of-place number a[i], we swap it with a[a[i]-1]. If this problem only wants to find a duplicate, this method works, However, the tricky part is that we want to find the first duplicate number for which the second occurance has the minimal index. Swapping destroys the order and is hard to recover.

The way to solve this problem is to mark the "proper index" negative. By this, take above array as an example, when we first see a[1] = 3, we mark a[a[1]-1] = a[2] as negative, if later we need to visit this index again, we know we have seen this number before.

def firstDuplicate(a):
    if not a: return -1
    for i in range(len(a)):
        proper_idx = abs(a[i]) - 1
        if a[proper_idx] < 0:
            # visited before
            return abs(a[i])
        else:
            a[proper_idx] = -a[proper_idx]
    return -1