Quick Overview

Check strict high-low alternation around a circular array, including equal neighbors, wraparound comparisons, and the two-element case.

Check Alternating Highs and Lows Around a Circular Array

Company: Capital One

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

An array is connected end to end to form a circle. Determine whether its values strictly alternate between a high point and a low point around the entire circle. Implement `is_alternating_circle(values: int[]) -> bool`. Every element must be strictly greater than both of its neighbors or strictly less than both of its neighbors. The first and last elements are neighbors. ### Constraints & Assumptions - There are between 2 and 200,000 elements, each between -1,000,000,000 and 1,000,000,000. - Equal neighboring values are not allowed in a valid alternating circle. - For length two, both neighbor positions of an element refer to the other element. Two distinct values therefore form a valid alternating circle. - Strict comparisons and the length-two convention are explicit practice choices for the reported high/low pattern. - Return one Boolean; no rotation or rearrangement of the input is allowed. ### Examples - `[1, 4, 2, 5]` returns `true`. Each low value has two higher neighbors and each high value has two lower neighbors, including across the last-to-first boundary. - `[1, 4, 2]` returns `false`. The value 2 is lower than 4 but higher than 1, so it is neither a high nor a low point. ```hint Include the closing edge A linearly alternating prefix does not prove the circle works. Check each value against both neighbors using wraparound indices. ```

Overview: Check strict high-low alternation around a circular array, including equal neighbors, wraparound comparisons, and the two-element case.

Read the full Capital One Software Engineer interview experience this question came from

An array is connected end to end to form a circle. Determine whether its values strictly alternate between a high point and a low point around the entire circle. Implement `is_alternating_circle(values: int[]) -> bool`. Every element must be strictly greater than both of its neighbors or strictly less than both of its neighbors. The first and last elements are neighbors. ### Constraints & Assumptions - There are between 2 and 200,000 elements, each between -1,000,000,000 and 1,000,000,000. - Equal neighboring values are not allowed in a valid alternating circle. - For length two, both neighbor positions of an element refer to the other element. Two distinct values therefore form a valid alternating circle. - Strict comparisons and the length-two convention are explicit practice choices for the reported high/low pattern. - Return one Boolean; no rotation or rearrangement of the input is allowed. ### Examples - `[1, 4, 2, 5]` returns `true`. Each low value has two higher neighbors and each high value has two lower neighbors, including across the last-to-first boundary. - `[1, 4, 2]` returns `false`. The value 2 is lower than 4 but higher than 1, so it is neither a high nor a low point. ```hint Include the closing edge A linearly alternating prefix does not prove the circle works. Check each value against both neighbors using wraparound indices. ```

Constraints

  • Values contains 2 through 200000 integers in [-1000000000,1000000000].
  • First and last entries are neighbors. Each value must be strictly above both neighbors or strictly below both.
  • Equal neighboring values are invalid; two distinct values form a valid length-two circle.
  • Return a boolean without rearranging the input.

Examples

Input: ([1, 4, 2, 5],)

Expected Output: True

Explanation: Every position is a strict local extremum including the closing edge.

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

Expected Output: False

Explanation: An odd alternating prefix can fail circular closure.

Loading coding console...

Show the approach

Approach

For each index, obtain previous and next indices with wraparound. Accept that element only if it is strictly greater than both neighbors or strictly smaller than both. These tests directly implement the definition, so all passing is sufficient and any failure is necessary evidence of invalidity. Strict comparison rejects neighboring equality, and checking every index includes the closing edge. At length two the previous and next indices coincide with the other element, making two distinct values valid exactly as specified. Numeric differences are unnecessary; comparisons avoid overflow concerns. One pass takes O(n) time and O(1) auxiliary state. No rotation or rearrangement is performed.

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