[Leetcode] Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

Analysis:

Pretty strait forward. Given num[-1] = num[n] = -∞ and num[i] ≠ num[i+1], if num[0] is greater than num[1], num[0] will be the peak since num[0] > num[1] and num[0] > num[-1]. If not, then num[1] could be the peak if num[1] > num[2], which could be computed in the next loop.  

    int findPeakElement(const vector &num) {
        if (num.size() == 1)
            return 0;
        int peak = 0;
        for(int i=1; i < num.size(); i++)
        {
            if (num[i] < num[peak])
                return i-1;
            else
                peak = i;
        }
        
        return peak;
    }

[Leetcode] Dungeon Game

The demons had captured the princess (P) and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of M x N rooms laid out in a 2D grid. Our valiant knight (K) was initially positioned in the top-left room and must fight his way through the dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons, so the knight loses health (negative integers) upon entering these rooms; other rooms are either empty (0's) or contain magic orbs that increase the knight's health (positive integers).

In order to reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Write a function to determine the knight's minimum initial health so that he is able to rescue the princess.

For example, given the dungeon below, the initial health of the knight must be at least 7 if he follows the optimal path RIGHT-> RIGHT -> DOWN -> DOWN.

-2 (K)	-3	3
-5	-10	1
10	30	-5 (P)

Notes:

• The knight's health has no upper bound.
• Any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

Analysis:

It is easy to know that at grid P, since " at any point his health point drops to 0 or below, he dies immediately", the remaining health value should be at least 1,  that is, initialHealth + dungeon >= 1, we have initialHealth = max(1, 1 - dungeon[i][j]).  (Notice, at any grid, the initial health should be at least 1 (for example,  test case [1,0,0] require initial health 1 even though it has positive remaining health at grid[0][1] and grid[0][2])

Similarly, to satisfy the initial health of dungeon[i][j], the initial health of dungeon[i-1][j] (or dungeon[i][j-1]) should be at least initialHealth[i-1][j] + dungeon[i-1][j] = initialHealth[i][j], that is, initialHealth[i][j] = initialHealth[i][j] - dungeon[i-1][j]. 

In addition, if grid[i][j] can go both grid[i+1][j] and grid[i][j+1] to P,  we should choose a path with less initial health between grid[i+1][j] and grid[i][j+1] since it require less initial health of grid[i][j].

We can simply code the solution by having the dynamic programming equations. 

         int calculateMinimumHP(vector &dungeon) {
        int m = dungeon.size();
        int n = dungeon[0].size();
        vector minInitHealth(m, vector<int>(n,0));
        for(int i=m-1; i>=0; i--)
        {
            for (int j=n-1; j>=0; j--)
            {
                if (i == m-1 && j == n-1)
                {
                    minInitHealth[i][j] = max(1, 1 - dungeon[i][j]);
                }  
                else if (i == m-1)
                {
                    minInitHealth[i][j] = max(1, minInitHealth[i][j+1] - dungeon[i][j]);
                }  
                else if (j == n-1)
                {
                    minInitHealth[i][j] = max(1, minInitHealth[i+1][j] - dungeon[i][j]);
                }  
                else
                {
                    minInitHealth[i][j] = max(1, min(minInitHealth[i+1][j],minInitHealth[i][j+1]) - dungeon[i][j]);
                }  
            }
        }
        
        return  minInitHealth[0][0];
    }

[Leetcode] Excel Sheet Column Title

Given a positive integer, return its corresponding column title as appear in an Excel sheet.

For example:

    1 -> A
    2 -> B
    3 -> C
    ...
    26 -> Z
    27 -> AA
    28 -> AB 

Analysis:
Similar to the problem of "Excel Sheet Column Number", we want to represent a number with 26 as base. The code is almost exactly same as converting a decimal number to string, eg: 1234 -> "1234", except that it is 26 base and beginning from 1 rather than 0 (decimal begins from 0 as 0-9). 

    string convertToTitle(int n) {
        string str = "";
        int k = 26;
        while(n > 0)
        {
            str.insert(str.begin(), (n - 1) % k + 'A');
            n = (n - 1) / k;
        }
        
        return str;
    }

[Leetcode] Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:

    A -> 1
    B -> 2
    C -> 3
    ...
    Z -> 26
    AA -> 27
    AB -> 28 

Analysis:

We know a number could be represented as binary, octal, decimal or hexadecimal. So what if we want to represent a number with 26 as base? We could represent 1 as A, 2 as B and Z as 26 which is exactly how an Excel column title works. 

It is pretty strait forward to convert a decimal represented string to a number, eg "123" = 1*100 + 2*10 + 3. Well, it is almost exactly the same for 26 based number as well, as the following code shows. 

    int titleToNumber(string s) {
        int n = 0;
        int k = 26;
        for(int i=0; i < s.size();i++)
        {
            n = n * k + (s[i] - 'A' + 1);
        }
        return n;
    } 

[Leetcode] Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Analysis:

As we know, n! = n * (n-1) * (n-2) * ... * 2 * 1. A simple way to get the trailing zeros is to calculate the value of n! and then count the trailing zeros. The problem is that the value of n! is too big to be hold by an integer. Even if we express the  n! using string, its time complexity is O(N), which does not satisfy the "logarithmic time complexity". 

Observed that every pair factor 5 and 2 of the number 1 to n will contribute a trailing zero for n!. Since from 1 to n, the number of  factor 2 is always greater than the factor of 5, the number of factor 5 is the number of trailing zeros. 

So the problem becomes how many of factor 5 among the number 1 to n. We know there are n/5 factor 5 from 1 to n (named 5, 10, 15, ...., floor(n/5) * 5) and there are n/25 extra factor of 5 (named 25, 50, 75, ... , floor(n/25)*25), and n/125 extra factor of 5, and so on. It is not so difficult to implement the code and the following code explains itself. One special case to handle is the k may be exceed the INT_MAX so better to use long to avoid overflow. 

    

    int trailingZeroes(int n) {
        int count = 0;
        long k = 5;
        while(n >= k)
        {
            count+=n/k;
            k*=5;
        }
        return count;
    }

[Leetcode] Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

Analysis:

An element m appearing more than n/2 times in the array means that the number of elements which is equal to m is greater than the ones which are different than m. So, if we increment the number by 1 for the m and decrement the number by for other different element, the element left which has count greater than 1 will be the majority element m. 

The code is very strait forward if you got the idea. The time complexity is O(n) since only one loop is needed. Pretty awesome, isn't it?

  int majorityElement(vector<int> &num) {
        int count = 0;
        int m;
        for(int i=0; i < num.size();i++)
        {
            if (count == 0)
            {
                m = num[i];
                count++;
            }
            else 
            {
                if (m != num[i])
                {
                    count--;
                }
                else
                {
                    count++;
                }
            }
        }
        return m;
    }

[Leetcode] Largest Number

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

Analysis:

An intuitive way to solve the problem is to sort the numbers by some order and then combine the numbers together by descending order.
The question is how should we sort the number? Apparently, it should not be sorted by the integer value. Given two numbers, how do we know which one is "bigger" in term of the combination results is bigger? It is pretty strait forward, just get the two string combinations and compare which one is bigger. For example, [12, 121], since 12121 is greater than 12112, 12121 is the number we want.
The code is pretty strait forward except don't forget to handle the special case of [0, 0], the result should be "0"  rather then "00" as there is no number of "00". 

    static int myComp(int num1, int num2)
    {
        string s1 = to_string(num1) + to_string(num2);
        string s2 = to_string(num2) + to_string(num1);
        return s1 < s2;
    }

    string largestNumber(vector &num) {
        sort(num.begin(), num.end(), myComp);
        //for case [0, 0], if max is 0, then return "0" rather than "00"
        if (num[num.size()-1] == 0)
            return "0";
        string s;
        for(int i=num.size()-1; i>=0; i--)
            s.append(to_string(num[i]));
            
        return s;
    }