Good day! Hope you are doing well. Today is July 13th, 2021. We are approaching midsummer. Not sure where time is going.
As I mentioned a few posts ago, I attempted some daily problems posted by LeetCode. At this time I am somewhat busy so I have missed a few. Hopefully in a month or two I will have enough time to work on a problem a day; at least the easy and medium. The others may take a couple days.
Today I looked at LeetCode 162 Find Peak Element.
A peak element is an element that is strictly greater than its neighbors. Given an integer array nums, find a peak element, and return its index. If the array contains multiple peaks, return the index to any of the peaks. You may imagine that nums[-1] = nums[n] = -∞. You must write an algorithm that runs in O(log n) time. Constraints: o 1 <= nums.length <= 1000 o -231 <= nums[i] <= 231 - 1 o nums[i] != nums[i + 1] for all valid i.
This looks like a modified binary search would work. Binary search meets the time complexity requirement.
We will attempt to solve this problem using the Java programming language and the VSCode IDE on a Windows computer. If you are just interested in solving the problem directly, the best approach is to use the on-line IDE provided by LeetCode. Since I am using a Windows platform, we will need to generate a test scaffold that will collect the input parameters, assign them to variables, call the function in question and display results. Please note that the test code IS NOT PART OF THE SOLUTION.
public int findPeakElement(int[] nums) {
}
The signature for the function of interest requires a single int[] array. We need to return the index of a peek value in the array.
1,2,3,1 main <<< nums: [1, 2, 3, 1] main <<< findPeakElement: 2 1,2,1,3,5,6,4 main <<< nums: [1, 2, 1, 3, 5, 6, 4] main <<< findPeakElement: 5 1,2,3,4,5,6,7 main <<< nums: [1, 2, 3, 4, 5, 6, 7] main <<< findPeakElement: 6 7,6,5,4,3,2,1 main <<< nums: [7, 6, 5, 4, 3, 2, 1] main <<< findPeakElement: 0
The first and only input line contains the integers for the `nums` array. Our test code reads the input, generates and then displays the array. This is done to verify that all is well so far.
At that point it seems that our test code calls the function of interest, computes the result and returns its value which is then displayed.
/**
* Test code.
* @throws IOException
*/
public static void main(String[] args) throws IOException {
// **** open buffered reader ****
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// **** read nums int[] array ****
int[] nums = Arrays.stream(br.readLine().trim().split(","))
.mapToInt(Integer::parseInt)
.toArray();
// **** close buffered reader ****
br.close();
// ???? ????
System.out.println("main <<< nums: " + Arrays.toString(nums));
// **** call function of interest and display result ****
System.out.println("main <<< findPeakElement: " + findPeakElement(nums));
}
Our test code seems to match very close our description of the test cases. I do not have much to add at this point.
/**
* A peak element is an element that is strictly greater than its neighbors.
* Given an integer array nums, find a peak element, and return its index.
* If the array contains multiple peaks, return the index to any of the peaks.
* You may imagine that nums[-1] = nums[n] = -∞.
* You must write an algorithm that runs in O(log n) time.
*
* 63 / 63 test cases passed.
* Status: Accepted
* Memory Usage: 40084000
*
* Eexcution: O(log(n)) Space: O(3) == O(1)
*/
static int findPeakElement(int[] nums) {
// **** initialization ***
int left = 0;
int right = nums.length - 1;
// **** binary search ****
while (left < right) {
// **** compute mid ****
int mid = left + (right - left) / 2;
// **** go right (line slope is positive) ****
if (nums[mid] < nums[mid + 1])
left = mid + 1;
// **** go left (line slope is negative) ****
else
right = mid;
}
// **** return peek index (left == right) ****
return left; // or right;
}
We are using a modified binary search approach.
We start by initializing a couple variables.
The main loop implements a binary search. We start by computing the mid value element in the current range in the array.
We then make the decision to go right or left. Note the expression used for the test. If the mid value in the array range is less than the next value to the right, the line has a positive slope and since we are looking for a peek (highest point) we need to use the right section so we move the left to the right. Otherwise we have encountered a negative slope and we need to go left. This is done by moving the right limit to the left by assigning mid to right.
When the condition in the while loop becomes false, then we have encountered a peek which should be the value in the left or right variables as illustrated in the code.
Information on performance has been written in the comments section of the function of interest.
Hope you enjoyed solving this problem as much as I did. The entire code for this project can be found in my GitHub repository.
If you have comments or questions regarding this, or any other post in this blog, please do not hesitate and leave me a note below. I will reply as soon as possible.
Keep on reading and experimenting. It is one of the best ways to learn, become proficient, refresh your knowledge and enhance your developer toolset.
Thanks for reading this post, feel free to connect with me John Canessa at LinkedIn.
Regards;
John