Values Already Home

MediumArrays & Hashing

Problem

A librarian checks a shelf nums before sorting it. A book at position i is already home if every book before it has a strictly smaller number and every book after it has a strictly larger number: sorting the shelf could never move it.

Return how many books are already home.

Example 1

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

Positions 0, 3 and 4 qualify; 3 and 2 are out of order with each other.

Example 2

Input:
nums = [5, 4, 3, 2, 1]
Output:
0

Example 3

Input:
nums = [7]
Output:
1

Constraints

  • 1 ≤ nums.length ≤ 10^5
  • -10^9 ≤ nums[i] ≤ 10^9

Hint

Show the first hint

'Every book before is smaller' only depends on the largest book before.

Walkthrough

How to approach it

01Clarify before coding

  • Strict comparisons? Yes: equal values on either side disqualify a position.
  • Is a single element home? Yes, both conditions hold vacuously.
  • Can values be negative? Yes; use sentinels like -infinity / +infinity for empty sides.

02Brute force

For each i, scan everything before and after it.

Cost: O(n²) time: 10^10 comparisons at n = 10^5.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.