FastPrep
Problem

Longest Arithmetic Subarray After One Change

Learn this problem
Amazon logoAmazonFULLTIMEOA
See Amazon hiring insights

Problem statement

You are given an integer array deviation.

You may change at most one element of the array to any integer value. After making at most one change, find the maximum possible length of a contiguous subarray that forms an arithmetic progression.

The changed element stays at its original index and may be used to connect the unchanged elements before it and after it into one longer arithmetic subarray.

A contiguous subarray forms an arithmetic progression if the difference between every pair of consecutive elements in that subarray is the same.

Function

longestArithmeticSubarrayAfterOneChange(deviation: int[]) → int

Examples

Example 1

deviation = [8, 5, 2, 1, 100]return = 4

Change 1 to -1. The contiguous subarray [8,5,2,-1] has common difference -3, so its length is 4.

Example 2

deviation = [1, 2, 3, 4, 100, 6, 7, 8, 9, 10]return = 10

Change 100 to 5. The entire array becomes an arithmetic progression with common difference 1.

Constraints

Constraints:

  • 1 <= deviation.length <= 105
  • -109 <= deviation[i] <= 109
  • You may change at most one element, and the changed value may be any integer.

More Amazon problems

drafts saved locally
public int longestArithmeticSubarrayAfterOneChange(int[] deviation) {
  // write your code here
}
deviation[8, 5, 2, 1, 100]
expected4
checking account