Introduction:
A popular question among LeetCoders and those interested in solving LeetCode questions is, "Are the easy questions really easy and the hard ones truly difficult?" In this blog post, I will share my experience of solving my first hard question on LeetCode, specifically the "Find in Mountain Array" problem (LeetCode problem #1095). Let's dive into it together!
Understanding the Problem: Before tackling any problem, it is crucial to thoroughly read and comprehend its requirements. Additionally, noting down any edge cases can be helpful. In the case of the "Find in Mountain Array" problem, our objective is to find the minimum position of a target number in an array. If the element is not found, we should return -1.
Key Points to Consider:
There are a few important details to keep in mind while approaching this problem:
Mountain Array: A mountain array is an array that first increases till it reaches a peak value, and then decreases. For example: [0, 1, 2, 4, 2, 1].
Peak Value: According to the problem, the peak value is the highest in the array, and it should not have any duplicates. In the example mentioned above, the peak value is 4.
Duplicate Elements: Other elements in the array can have duplicate values, but these duplicates cannot be adjacent to each other. For instance: [1, 2, 3, 4, 5, 3, 1]. Here, the peak value is 5, and element 3 has two duplicate values that can be found on different sides of the peak element.
Accessing Array Elements: Instead of providing the array directly, the problem offers an interface to access the elements using the "mountainArr.get(index)" method, and the length of the array is given by "mountainArray.length()".
Approach to Solve the Problem:
Having understood the problem's details, let's discuss our approach to solving it. Initially, one might consider using linear search, which is a valid intuition. However, there's a constraint to be aware of. If you refer to the provided statement, it mentions that :-
"Submissions making more than 100 calls to MountainArray.get will be judged Wrong Answer."
Consequently, we cannot make more than 100 calls to "MountainArray.get()". Therefore, employing linear search (which requires multiple calls to "MountainArray.get()" for each search) would be incorrect for this problem as some array in the test samples has more than 100 element.
To avoid exceeding the limit of 100 calls to ".length()" method, we must utilize binary search, which has a time complexity of log(n). For instance, if the array size is 10,000, the ".length()" method will be called approximately 14 times in the worst-case scenario.
Challenge:
Applying Binary Search to a Mountain Array Binary search can only be used on sorted arrays in increasing or decreasing order. However, a mountain array has both a sorted increasing part and a sorted decreasing part. For example: [0, 1, 2, 4, 2, 1]. From index 0 to 3, the array increases, and from index 3 to 5, it decreases. The element at index 3 is the peak value. The key takeaway here is that the array always increases until it reaches the peak value, and it always decreases from the peak value to the last element.
The Solution Algorithm: To solve the problem, we can follow these steps:
Find the peak element: We can employ a modified binary search to locate the peak element. Let's use the array [0, 1, 2, 4, 2, 1] as an example. Initialize the start, mid, and end pointers as follows:
Start = 0
End = length of the array - 1
Mid = start + (end - start) / 2 (This prevents integer overflow in statically typed languages.)
During the search, we encounter two major conditions:
a) If the element at the mid index is greater than the element at mid + 1, it means we have found a potential peak. In this case, we set the end element to the mid index since the mid value can also be the peak value due to its higher value.
b) If the element at the mid index is less than the element at mid + 1, it implies that we need to move towards higher values. Thus, we update the start pointer to mid + 1.
The search continues within a while loop until the start becomes equal to or greater than the end. After exiting the loop, the start pointer will be pointing to the peak element. Let's consider the simple example of [0, 1, 0] to illustrate this process:
Step 1: Start = 0, End = 2, Mid = 1. The element at the mid index (1) is greater than the element at mid + 1 (0). Hence, End = 1.
Step 2: Start = 0, End = 1, Mid = 0. Start < End? Yes, so we proceed. The element at the mid index (0) is less than the element at mid + 1 (1). Therefore, we update Start = Mid + 1 = 1.
Step 3: Start = 1, End = 1, Mid = 0. Start < End? No, so the loop breaks and the start pointer remains 1. From this, we can observe that the peak value (1) is found at index 1.
int start = 0;
int end = mountainArr.length() - 1;
//finding the peak
while (start < end){
int mid = start + (end - start) / 2;
if (mountainArr.get(mid) > mountainArr.get(mid + 1)){
end = mid;
}
else{
start = mid + 1;
}
}
int peak = start;
It is advisable to use pen and paper to gain a better understanding of how the algorithm functions in different scenarios.
Continuation:
Now that we have identified the index of the peak value, the next step is to split the array into two parts. The first part consists of elements from the start to the peak value, while the second part contains elements from the next element after the peak value to the last element in the array. We can then apply binary search to the first part. If the target element is found there, we return its index. Otherwise, we search for the second part. If the target is not found after searching both parts, it means the target does not exist in the array, and we return -1, as instructed.
It is important to note that both searching for the peak element and searching for the target element in the two parts of the array has a time complexity of log(n).
start = 0;
end = peak;
while (start <= end){
int mid = start +(end - start) / 2;
if (mountainArr.get(mid) == target){
return mid;
}else if(mountainArr.get(mid) < target){
start = mid + 1;
}else{
end = mid - 1;
}
}
start = peak;
end = mountainArr.length() - 1;
while (start <= end){
int mid = start +(end - start) / 2;
if (mountainArr.get(mid) == target){
return mid;
}else if(mountainArr.get(mid) < target){
end = mid - 1;
}else{
start = mid + 1;
}
}
return -1;
Conclusion: After successfully solving this problem and gaining experience in solving various difficulties (easy, medium, and hard) on LeetCode, I can confidently say that the difficulty tag attached to each problem may not always reflect their true complexity. With a solid foundation in data structures and algorithms, coupled with consistent practice, any problem can become manageable but, without that, the question tagged easy will be a nightmare to solve. Remember, if you know how to search for a peak value efficiently and are familiar with binary search, this problem will be a piece of cake.
You can find the Java and C++ code for this solution here
In case you need a refresher on binary search algorithms, you can watch this here on Kunal Kushwaha's youtube channel and explore his DSA playlist to learn more about data structures and algorithms.
Links to leetcode :- https://leetcode.com/