leetcode 1095. Find in Mountain Array (hard) : NileshBlog.Tech

Welcome, fellow coding enthusiasts! Today, we’re going to embark on an exciting journey into the world of Leetcode and explore the fascinating problem of “leetcode 1095.” or “Find in Mountain Array.” In this blog post, we’ll break down this problem, guide you through the concept of Mountain Arrays, and provide a solution to tackle it. So, grab your coding gear, and let’s get started!

Table of Contents

What is Leetcode 1095?

Leetcode 1095. is a challenging coding problem that falls under the category of “Hard” on the Leetcode platform. It involves searching for a target element in an array that’s structured like a mountain. But what exactly is a Mountain Array?

Understanding Mountain Arrays

Before we dive into the problem, let’s grasp the concept of a Mountain Array. Imagine a mountain where you start from the base, climb to the peak, and then descend back. In terms of an array, this means we have a sequence of integers that first increase and then decrease. So, it’s like ascending from the left side of the array and descending from the right side.

Now, the challenge in Leetcode 1095 is to find a target element within this mountain array efficiently. It’s like navigating your way up and down the mountain to locate a hidden treasure, which, in our case, is the target element.

The Structure of a Mountain Array

Here’s an example of what a mountain array might look like:

Index	0	1	2	3	4	5	6	7
Value	1	5	9	15	20	13	7	2

In this example, the mountain array first increases until index 4 and then starts decreasing from index 5. It’s crucial to recognize this structure to efficiently solve the problem.

Mountain Array Example

Index	0	1	2	3	4	5	6	7
Value	1	5	9	15	20	13	7	2

Now, let’s break down the code using this example.

Step-by-Step Explanation

Step	Operation	Subarray	Updated Range	Middle Index	Middle Value	Target	Explanation
1.	Find Peak	–	[0, 7]	3	15	–	The peak is at index 3 with a value of 15.
2.	Left Binary Search	Left (0, 3)	[0, 2]	1	5	–	Target not found; continue to the right.
3.	Right Binary Search	Right (4, 7)	[4, 7]	6	7	–	Target not found; continue to the right.
4.	Right Binary Search	Right (4, 7)	[6, 7]	7	2	–	Target found at index 7.

dry and run to solve

This table visually represents the mountain array, the subarrays being searched, and the steps taken to find the target. In this example, the target (if any) is searched within the specified subarrays.

The Challenge

Now, let’s get to the heart of the matter: solving Leetcode 1095. We need to find the target element in the given mountain array. To make it more interesting, we don’t have direct access to the entire array. We can only use three operations:

get(index): This function allows us to access the value at a specific index in the mountain array.
MountainArray.length(): We can use this function to find the length of the mountain array.
findInMountainArray(target): Our goal is to implement this function and return the index of the target element if it exists, or -1 if it’s not present in the array.

A High-Level Approach

So, how do we tackle this problem? Let’s outline a step-by-step approach:

Find the peak element in the mountain array. This step is crucial as it divides the array into two subarrays: one that is strictly increasing, and one that is strictly decreasing.
Conduct binary searches in both subarrays to find the target element.

Codes : Binary Search Appraoch – Leetcode 1095. Find in Mountain Array

The C++ Code

We’re finally here, ready to dive into some code. Below is the full C++ code to solve Leetcode 1095:

class Solution {
public:
    int findInMountainArray(int target, MountainArray &mountainArr) {
        int peak = findPeak(mountainArr);

        int left_result = binarySearch(target, mountainArr, 0, peak, true);
        if (left_result != -1) return left_result;

        return binarySearch(target, mountainArr, peak + 1, mountainArr.length() - 1, false);
    }

    int findPeak(MountainArray &mountainArr) {
        int left = 0, right = mountainArr.length() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    int binarySearch(int target, MountainArray &mountainArr, int left, int right, bool ascending) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int mid_val = mountainArr.get(mid);

            if (mid_val == target) {
                return mid;
            } else if ((mid_val < target) == ascending) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
};

Java:

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        int peak = findPeak(mountainArr);

        int leftResult = binarySearch(target, mountainArr, 0, peak, true);
        if (leftResult != -1) return leftResult;

        return binarySearch(target, mountainArr, peak + 1, mountainArr.length() - 1, false);
    }

    public int findPeak(MountainArray mountainArr) {
        int left = 0, right = mountainArr.length() - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            if (mountainArr.get(mid) < mountainArr.get(mid + 1)) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        return left;
    }

    public int binarySearch(int target, MountainArray mountainArr, int left, int right, boolean ascending) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int midVal = mountainArr.get(mid);

            if (midVal == target) {
                return mid;
            } else if ((midVal < target) == ascending) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return -1;
    }
}

Python:

class Solution:
    def findInMountainArray(self, target, mountainArr):
        peak = self.findPeak(mountainArr)

        left_result = self.binarySearch(target, mountainArr, 0, peak, True)
        if left_result != -1:
            return left_result

        return self.binarySearch(target, mountainArr, peak + 1, mountainArr.length() - 1, False)

    def findPeak(self, mountainArr):
        left, right = 0, mountainArr.length() - 1

        while left < right:
            mid = left + (right - left) // 2
            if mountainArr.get(mid) < mountainArr.get(mid + 1):
                left = mid + 1
            else:
                right = mid

        return left

    def binarySearch(self, target, mountainArr, left, right, ascending):
        while left <= right:
            mid = left + (right - left) // 2
            mid_val = mountainArr.get(mid)

            if mid_val == target:
                return mid
            elif (mid_val < target) == ascending:
                left = mid + 1
            else:
                right = mid - 1

        return -1

JavaScript:

const findInMountainArray = (target, mountainArr) => {
  const len = mountainArr.length();

  let peakIdx = 0;
  let l = 0;
  let r = len;
  while (l < r) {
    const m = ~~((l + r) / 2);
    if (mountainArr.get(m) < mountainArr.get(m + 1)) l = peakIdx = m + 1;
    else r = m;
  }

  l = 0;
  r = peakIdx - 1;
  while (l <= r) {
    const m = ~~((l + r) / 2);
    if (mountainArr.get(m) === target) return m;
    else if (mountainArr.get(m) < target) l = m + 1;
    else r = m - 1;
  }

  l = peakIdx;
  r = len - 1;
  while (l <= r) {
    const m = ~~((l + r) / 2);
    if (mountainArr.get(m) === target) return m;
    else if (mountainArr.get(m) > target) l = m + 1;
    else r = m - 1;
  }
  return -1;
};

Conclusion

In this blog post, we’ve explored the intriguing Leetcode 1095 problem, delved into the concept of Mountain Arrays, and provided a full C++ code solution to tackle it. With the knowledge gained here, you’re well-equipped to take on this challenge and navigate your way through the peaks and valleys of Mountain Arrays.

Remember, coding is like solving puzzles, and Leetcode problems like these are excellent exercises to sharpen your problem-solving skills. So, put your coding hat on, practice, and soon you’ll be conquering even more challenging problems with ease.

Happy coding! 🚀

leetcode 1095. Find in Mountain Array (hard)