Peak and Pride

-

Problem is here: https://leetcode.com/problems/peak-index-in-a-mountain-array/description/

Let's call an array A a mountain if the following properties hold:
  • A.length >= 3
  • There exists some 0 < i < A.length - 1 such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Given an array that is definitely a mountain, return any i such that A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1].
Example 1:
Input: [0,1,0]
Output: 1
Example 2:
Input: [0,2,1,0]
Output: 1

If you play close attention to the problem, it actually ends up being much simpler than the whole problem statement suggests. Since the input is confirmed to be a mountain (hence you don’t need to check whether it is a mountain or not), then all you really need is to find the max element in the array! Now even if the question was to determine whether the input was a mountain or not, you could still find the max and then do an O(n) to determine whether that max is the peak of the mountain or not. Code is below. 

Below you’ll also find a screenshot of our Pride Month experience (click here to check it out: www.bing.com and type “pride mon”). This is a tiny way to celebrate diversity, inclusion and equality during these times when these values are not being properly celebrated by many of our politicians. Cheers, Boris.





               public class Solution
               {
                              public int PeakIndexInMountainArray(int[] A)
                              {
                                             int max = Int32.MinValue;
                                             int maxIndex = -1;
                                             for (int i = 0; i < A.Length; i++)
                                             {
                                                            if (A[i] > max)
                                                            {
                                                                           max = A[i];
                                                                           maxIndex = i;
                                                            }
                                             }
                                             return maxIndex;
                              }
               }

Comments

  1. Prithvi ShankarJune 21, 2018 at 6:05 PM

    Nice simple solution. Although, I think you can do a binary search to find the max element to solve it in O(log n). :-)

    ReplyDelete
    Replies
    1. Boris VasilenkoJune 21, 2018 at 6:33 PM

      Yeah thinking about it more and knowing that the mountain property is guaranteed, I think you’re right!

      Delete
  2. TarasJune 21, 2018 at 11:22 PM

    An excellent observation, Boris! The C++ implementation of this idea is, as always, more concise than C# :P and looks like:

    class Solution {
    public:
    int peakIndexInMountainArray(const vector& A) {
    return distance(A.cbegin(), max_element(A.cbegin(), A.cend()));
    }
    };

    but a slightly more verbose implementation below takes advantage of another observation - for a given index i if an element to its left is greater or equal to it, a peak could only be on its left (i-1 or further to its left), if an element to its right is less than or equal to it, a peak could only be on its right (i+1 or further to its right) and otherwise A[i-1] < A[i] > A[i+1] and we have found the peak. The code is:

    class Solution {
    public:
    int peakIndexInMountainArray(const vector& A) {
    int left = 1;
    int right = A.size() - 2;
    while (left <= right) {
    int mid = left + (right - left) / 2;
    if (A[mid-1] >= A[mid]) {
    right = mid - 1;
    } else if (A[mid] <= A[mid+1]) {
    left = mid + 1;
    } else {
    return mid;
    }
    }
    return -1;
    }
    };

    https://leetcode.com/problems/peak-index-in-a-mountain-array/discuss/141301/log(N)-solution-based-on-binary-search-in-C++.

    Cheers,
    Taras

    ReplyDelete

Post a Comment

Popular posts from this blog

Count Binary Substrings

-
Image
Problem by Leetcode:  https://leetcode.com/problems/count-binary-substrings/description/ Give a string  s , count the number of non-empty (contiguous) substrings that have the same number of 0's and 1's, and all the 0's and all the 1's in these substrings are grouped consecutively. Substrings that occur multiple times are counted the number of times they occur. Example 1: Input: "00110011" Output: 6 Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01". Notice that some of these substrings repeat and are counted the number of times they occur. Also, "00110011" is not a valid substring because all the 0's (and 1's) are not grouped together. Example 2: Input: "10101" Output: 4 Explanation: There are 4 substrings: "10", "01", "10", "01&
Read more

Count Vowels Permutation: Standard DP

-
Image
Standard DP problem:  https://leetcode.com/problems/count-vowels-permutation/ Given an integer  n , your task is to count how many strings of length  n  can be formed under the following rules: Each character is a lower case vowel ( 'a' ,  'e' ,  'i' ,  'o' ,  'u' ) Each vowel  'a'  may only be followed by an  'e' . Each vowel  'e'  may only be followed by an  'a'  or an  'i' . Each vowel  'i'   may not  be followed by another  'i' . Each vowel  'o'  may only be followed by an  'i'  or a  'u' . Each vowel  'u'  may only be followed by an  'a'. Since the answer may be too large, return it modulo  10^9 + 7. Example 1: Input: n = 1 Output: 5 Explanation: All possible strings are: "a", "e", "i" , "o" and "u". Example 2: Input: n = 2 Output: 10 Explanation: All possible strings are
Read more

Maximum Number of Balloons

-
Image
#431 in my solved list:  https://leetcode.com/problems/maximum-number-of-balloons/ Given a string  text , you want to use the characters of  text  to form as many instances of the word  "balloon"  as possible. You can use each character in  text   at most once . Return the maximum number of instances that can be formed.   Example 1: Input: text = "nlaebolko" Output: 1 Example 2: Input: text = "loonbalxballpoon" Output: 2 Example 3: Input: text = "leetcode" Output: 0 Constraints: 1 <= text.length <= 10^4 text  consists of lower case English letters only. Solution is as follows:  - Count the number of occurrences of the "balloon" letters in the input string  - For "l" and "o", divide the count by 2  - If the balloon string is not fully covered, return 0  - Return the min number across all occurrences Code is below, cheers, ACC. public class Solution {     public int M
Read more