FastPrepLongest Increasing Subsequence With Bounded Adjacent Difference
Problems/Longest Increasing Subsequence With Bounded Adjacent Difference

Longest Increasing Subsequence With Bounded Adjacent Difference

Google logoGoogle● HardFULLTIMEPHONE SCREEN

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report describes a phone-screen task: the longest increasing subsequence where the difference between neighbors is limited. We reuse the function signature, the examples, and the limits from an equivalent task we already reviewed. Our version is about 95% the same as the reported question.

Given a non-empty integer array arr and a non-negative integer k, return the maximum length of a subsequence that satisfies all of the following:

  • The selected values are strictly increasing.
  • The difference between every pair of consecutive selected values is at most k.
  • The selected values preserve their relative order in arr.

A subsequence may delete any number of elements without changing the order of the remaining elements.

Function

longestBoundedIncreasingSubsequence(arr: int[], k: int) → int

Examples

Example 1

arr = [7,1,4,5,8,8,10,6,7,7,7,8]k = 4return = 6

One longest valid subsequence is [1,4,5,6,7,8]. It preserves input order, every adjacent difference is at most 4, and its length is 6.

Example 2

arr = [3,1,2,6,10,11,4,5]k = 3return = 4

The subsequence [1,2,4,5] is strictly increasing, preserves input order, and has adjacent differences 1, 2, and 1.

Example 3

arr = [5,4,3,2,1]k = 2return = 1

No two values form a strictly increasing pair in subsequence order, so every valid longest subsequence contains one value.

Constraints

  • 1 <= arr.length <= 2 * 10^5
  • -10^9 <= arr[i] <= 10^9
  • 0 <= k <= 2 * 10^9

More Google Phone Screen questions

  • Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
  • Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
  • Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
  • Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
  • Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
  • Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
  • Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026

Similar questions at other companies

  • Longest Increasing Subsequence With Bounded Adjacent DifferenceAmazon · PHONE SCREEN · ONSITE INTERVIEW
  • Minimum Sorted Erasure OperationsAtlassian · OAAtlassian interview questions
  • Minimum Bridge TurnbacksBNSF Railway · OABNSF Railway interview questions
  • Maximum Profit from an Increasing Price TripletOdoo · OAOdoo interview questions
  • Split Array to Minimize the Largest SumNation with NaMo · PHONE SCREEN
  • Trapping Rain WaterOracle · PHONE SCREENOracle interview questions
  • Minimum Length After Removing Arithmetic TriplesMedia.net · PHONE SCREEN
  • Select Transactions with Child-Pays-for-Parent PackagesCoinbase · PHONE SCREENCoinbase interview questions
  • Longest Increasing Path in a MatrixNew Relic · PHONE SCREEN · ONSITE INTERVIEW
  • Maximum Profit with at Most K TransactionsTekion · PHONE SCREENTekion interview questions

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
  • Google L4 SWE Phone Screen and Kirkland Onsite: 1 Experience
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int longestBoundedIncreasingSubsequence(int[] arr, int k) {
      // write your code here
    }
}
Checking account…