Quick Overview

Google new-grad onsite coding problem: given an array that strictly rises to one peak and then strictly falls, return the smallest index holding a target value, or -1 if it is absent. Tests searching a non-monotonic array while reading far fewer elements than it holds.

First Index of a Target in a Strictly Rising-Then-Falling Array

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

An array is a mountain when it has at least three elements and a peak index `i` with `0 < i < len(arr) - 1` such that the values strictly increase from `arr[0]` up to `arr[i]` and strictly decrease from `arr[i]` to the last element. Given a mountain array and a target value, return the smallest index at which the target occurs, or `-1` if it does not occur. The report describes this round as a variant of known tasks about finding a mountain array's peak and searching a mountain array, without saying what the variant changed; this version poses the base search task. ### Function Signature ```python def find_in_mountain(arr: list[int], target: int) -> int: ``` ### Rules - `arr` is guaranteed to be a mountain as defined above. - Because each side of the peak is strictly monotonic, the target occurs at most twice. Return the smaller index when it occurs twice. - Return `-1` when the target does not occur. - Treat reading an element as expensive: the task expects far fewer reads than `len(arr)`. The console checks only the returned index. ### Constraints - `3 <= len(arr) <= 10^5` - `0 <= arr[i] <= 10^9` - `0 <= target <= 10^9` ### Examples **Example 1** ```text Input: arr = [1, 2, 3, 4, 5, 3, 1], target = 3 Output: 2 ``` The value 3 appears at index 2 on the rising side and at index 5 on the falling side; the smaller index is 2. **Example 2** ```text Input: arr = [0, 1, 2, 4, 2, 1], target = 3 Output: -1 ``` **Example 3** ```text Input: arr = [1, 5, 9, 7, 6, 2], target = 6 Output: 4 ``` The value 6 appears only on the falling side, at index 4.

Overview: Google new-grad onsite coding problem: given an array that strictly rises to one peak and then strictly falls, return the smallest index holding a target value, or -1 if it is absent. Tests searching a non-monotonic array while reading far fewer elements than it holds.

An array is a **mountain** when it has at least three elements and there is a peak index `i` with `0 < i < len(arr) - 1` such that the values strictly increase from `arr[0]` up to `arr[i]` and strictly decrease from `arr[i]` to the last element. Given a mountain array `arr` and an integer `target`, return the smallest index at which `target` occurs in `arr`, or `-1` if it does not occur. ### Rules - `arr` is guaranteed to be a mountain as defined above. - Because each side of the peak is strictly monotonic, `target` occurs at most twice. When it occurs twice, return the smaller index. - Return `-1` when `target` does not occur. - Treat reading an element as expensive: aim for far fewer element reads than `len(arr)`. The console checks only the returned index. ### Example 1 ```text Input: arr = [1, 2, 3, 4, 5, 3, 1], target = 3 Output: 2 ``` The value 3 appears at index 2 on the rising side and at index 5 on the falling side; the smaller index is 2. ### Example 2 ```text Input: arr = [1, 5, 9, 7, 6, 2], target = 6 Output: 4 ``` The value 6 appears only on the falling side, at index 4. ### Constraints - `3 <= len(arr) <= 10^5` - `0 <= arr[i] <= 10^9` - `0 <= target <= 10^9` - `arr` is a mountain array. Every value and the returned index fit in a 32-bit signed integer (`int` in Java and C++).

Constraints

  • 3 <= len(arr) <= 10^5
  • 0 <= arr[i] <= 10^9
  • 0 <= target <= 10^9
  • arr is a mountain: there is a peak index i with 0 < i < len(arr) - 1, values strictly increase from arr[0] to arr[i] and strictly decrease from arr[i] to the last element
  • Every value and the returned index fit in a 32-bit signed integer

Examples

Input: ([1, 3, 2], 1)

Expected Output: 0

Explanation: Minimum length 3; target at index 0, the start of the rising side.

Input: ([1, 3, 2], 3)

Expected Output: 1

Explanation: Minimum length 3; target equals the peak value at index 1.

Hints

  1. Each side of the peak is strictly monotonic: one side is sorted ascending and the other descending. Comparing an element with its right neighbour tells you which side it is on.
  2. Any occurrence on the rising side has a smaller index than any occurrence on the falling side, so the rising side decides the answer whenever it contains the target.
  3. Check the boundaries: the target may equal the peak value, or sit at index 0 or at the last index.

Smallest Index of a Target in a Mountain Array

mediumGoogleSoftware Engineer

An array is a mountain when it has at least three elements and there is a peak index i with 0 < i < len(arr) - 1 such that the values strictly increase from arr[0] up to arr[i] and strictly decrease from arr[i] to the last element.

Given a mountain array arr and an integer target, return the smallest index at which target occurs in arr, or -1 if it does not occur.

Rules

  • arr is guaranteed to be a mountain as defined above.
  • Because each side of the peak is strictly monotonic, target occurs at most twice. When it occurs twice, return the smaller index.
  • Return -1 when target does not occur.
  • Treat reading an element as expensive: aim for far fewer element reads than len(arr). The console checks only the returned index.

Example 1

Input:  arr = [1, 2, 3, 4, 5, 3, 1], target = 3
Output: 2

The value 3 appears at index 2 on the rising side and at index 5 on the falling side; the smaller index is 2.

Example 2

Input:  arr = [1, 5, 9, 7, 6, 2], target = 6
Output: 4

The value 6 appears only on the falling side, at index 4.

Constraints

  • 3 <= len(arr) <= 10^5
  • 0 <= arr[i] <= 10^9
  • 0 <= target <= 10^9
  • arr is a mountain array.

Every value and the returned index fit in a 32-bit signed integer (int in Java and C++).

Examples

Example 1
Input
([1, 3, 2], 1)
Output
0
Notes
Minimum length 3; target at index 0, the start of the rising side.
Example 2
Input
([1, 3, 2], 3)
Output
1
Notes
Minimum length 3; target equals the peak value at index 1.

Constraints

  • •3 <= len(arr) <= 10^5
  • •0 <= arr[i] <= 10^9
  • •0 <= target <= 10^9
  • •arr is a mountain: there is a peak index i with 0 < i < len(arr) - 1, values strictly increase from arr[0] to arr[i] and strictly decrease from arr[i] to the last element
  • •Every value and the returned index fit in a 32-bit signed integer

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def find_in_mountain(arr: list[int], target: int) -> int:
Sample call
find_in_mountain([1, 3, 2], 1)
Language
Case 1
Input
([1, 3, 2], 1)
Expected
0
Case 2
Input
([1, 3, 2], 3)
Expected
1

Browse More Questions

Show the approach

Approach

Three binary searches. (1) Find the peak: keep the invariant that the peak index lies in [lo, hi]. For mid < hi, adjacent values in a mountain are never equal, so if arr[mid] < arr[mid + 1] then mid is on the rising side strictly before the peak and lo = mid + 1 keeps the peak in range; otherwise arr[mid] > arr[mid + 1], mid is at or after the peak, and hi = mid keeps it. The range shrinks every step and ends with lo == hi == peak. (2) Search the ascending run arr[0..peak] (peak included) with an ordinary binary search. Every rising-side index is smaller than every falling-side index, and the strictly increasing run holds the value at most once, so a hit here is the smallest index and is returned immediately. (3) Otherwise search the descending run arr[peak+1..n-1] with the comparisons reversed; the strictly decreasing run holds the value at most once. (4) If neither search finds the target, return -1. Edge cases: a target equal to the peak value is found by step 2 because its range includes the peak; a target at index 0 or the last index is reached because both ranges are inclusive; a peak at index 1 or n-2 leaves a one-element side that the inclusive bounds still cover; values below the minimum or above the peak simply exhaust both searches. The whole method reads about 3 log2 n elements, far fewer than len(arr).

Time complexity:
O(log n)
Space complexity:
O(1)