Longest Increasing Subsequence With Bounded Adjacent Difference
Updated
Problem statement
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) → intExamples
Example 1
arr = [7,1,4,5,8,8,10,6,7,7,7,8]k = 4return = 6One 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 = 4The 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 = 1No 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^90 <= 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