Posts

Showing posts from June, 2018

Peak and Pride

Image
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

Backspace String Compare, by LeetCode

Image
Problem is labeled as easy by LeetCode, here it is:  https://leetcode.com/problems/backspace-string-compare/description/ : Given two strings  S  and  T , return if they are equal when both are typed into empty text editors.  #  means a backspace character. Example 1: Input: S = "ab#c" , T = "ad#c" Output: true Explanation : Both S and T become "ac". Example 2: Input: S = "ab##" , T = "c#d#" Output: true Explanation : Both S and T become "". Example 3: Input: S = "a##c" , T = "#a#c" Output: true Explanation : Both S and T become "c". Example 4: Input: S = "a#c" , T = "b" Output: false Explanation : S becomes "c" while T becomes "b". My solution won't be the most efficient - it will run in O(n)-time and O(n)-space. There is a way to do in O(1)-space but this is a straightforward problem to use a stack that I decided to use i