Longest Arithmetic Subsequence

🎯

Longest Arithmetic Subsequence

mediumHASH_MAPAmazonGoogle

Imagine you are analyzing stock prices over days and want to find the longest period where the price changes by a fixed amount each day. This problem helps you identify such consistent trends.

💡 This problem requires tracking relationships between elements based on their differences, which can be confusing at first. Beginners often struggle to realize that the key is to track the length of arithmetic subsequences ending at each index with a given difference, rather than just values.

📋

Problem Statement

Given an integer array nums, return the length of the longest arithmetic subsequence in nums. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements. An arithmetic subsequence is a subsequence where the difference between consecutive elements is the same.

1 ≤ nums.length ≤ 10^50 ≤ nums[i] ≤ 10^4

💡

Example

Input"[3, 6, 9, 12]"

Output4

The whole array is an arithmetic sequence with difference 3.

Input"[9, 4, 7, 2, 10]"

Output3

The longest arithmetic subsequence is [4, 7, 10] with difference 3.

Input"[20, 1, 15, 3, 10, 5, 8]"

Output4

One longest arithmetic subsequence is [20, 15, 10, 5] with difference -5.

• Single element array → output 1
• All elements equal → output equals array length
• Array with no arithmetic subsequence longer than 2 → output 2
• Large array with repeated elements and multiple differences → output correct max length

⚠️

Common Mistakes

Not initializing max length properly

Returns 0 or incorrect length for small inputs

✅ Initialize max length to 2 if array length >= 2, else to array length

Using nested loops but not tracking difference lengths in dp

Code runs but returns incorrect results or TLE

✅ Use a hash map per index to store lengths keyed by difference

Updating dp[i][diff] without taking max with existing value

Overwrites longer subsequences with shorter ones, causing wrong max length

✅ Use max(dp[i][diff], new_length) when updating

Confusing subsequence with subarray

Trying to find contiguous sequences only, missing valid subsequences

✅ Remember subsequences can skip elements; do not require contiguous indices

Not handling single element or empty array edge cases

Runtime errors or wrong output

✅ Add checks for array length and return accordingly

🧠

Brute Force (Nested Loops Checking All Subsequences)

💡 Starting with brute force helps understand the problem's nature by explicitly checking all subsequences, even though it's inefficient. It builds intuition about what defines an arithmetic subsequence.

Intuition

Try every pair of elements as a start and check subsequent elements to see if they continue the arithmetic pattern. Track the longest such subsequence found.

Algorithm

1. For each pair of indices (i, j), compute the difference d = nums[j] - nums[i].
2. Initialize length = 2 for this pair as the start of an arithmetic subsequence.
3. Iterate over the rest of the array to find elements that continue the sequence with difference d.
4. Update the maximum length found.

💡 This approach is straightforward but involves nested loops and repeated scanning, which can be hard to optimize without tracking state.

</>

Code

def longestArithSeqLength(nums):
    n = len(nums)
    max_len = 2 if n >= 2 else n
    for i in range(n):
        for j in range(i+1, n):
            diff = nums[j] - nums[i]
            length = 2
            next_val = nums[j] + diff
            for k in range(j+1, n):
                if nums[k] == next_val:
                    length += 1
                    next_val += diff
            max_len = max(max_len, length)
    return max_len

# Example usage
if __name__ == '__main__':
    print(longestArithSeqLength([3,6,9,12]))  # Output: 4

Line Notes

n = len(nums)Determine the size of the input array to control loops

max_len = 2 if n >= 2 else nInitialize max length; minimum arithmetic subsequence length is 2 if possible

for i in range(n)Outer loop picks the first element of the subsequence

for j in range(i+1, n)Inner loop picks the second element to define the difference

diff = nums[j] - nums[i]Calculate the common difference for this subsequence

length = 2Start counting length from the initial pair

next_val = nums[j] + diffNext expected value to continue the arithmetic sequence

for k in range(j+1, n)Scan remaining elements to find continuation of the sequence

if nums[k] == next_valCheck if current element continues the arithmetic progression

length += 1Increment length when sequence continues

next_val += diffUpdate next expected value

max_len = max(max_len, length)Update global maximum length found

return max_lenReturn the longest arithmetic subsequence length found

import java.util.*;
public class Solution {
    public static int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        int maxLen = n >= 2 ? 2 : n;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int diff = nums[j] - nums[i];
                int length = 2;
                int nextVal = nums[j] + diff;
                for (int k = j + 1; k < n; k++) {
                    if (nums[k] == nextVal) {
                        length++;
                        nextVal += diff;
                    }
                }
                maxLen = Math.max(maxLen, length);
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestArithSeqLength(new int[]{3,6,9,12})); // Output: 4
    }
}

Line Notes

int n = nums.length;Get array length for loop bounds

int maxLen = n >= 2 ? 2 : n;Initialize max length with minimum valid subsequence length

for (int i = 0; i < n; i++)Outer loop selects first element

for (int j = i + 1; j < n; j++)Inner loop selects second element to define difference

int diff = nums[j] - nums[i];Calculate difference for arithmetic subsequence

int length = 2;Start length count from initial pair

int nextVal = nums[j] + diff;Next expected value in sequence

for (int k = j + 1; k < n; k++)Scan remaining elements for continuation

if (nums[k] == nextVal)Check if current element continues the sequence

length++;Increment length when sequence continues

nextVal += diff;Update next expected value

maxLen = Math.max(maxLen, length);Update global max length

return maxLen;Return final answer

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int longestArithSeqLength(vector<int>& nums) {
    int n = nums.size();
    int maxLen = n >= 2 ? 2 : n;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int diff = nums[j] - nums[i];
            int length = 2;
            int nextVal = nums[j] + diff;
            for (int k = j + 1; k < n; k++) {
                if (nums[k] == nextVal) {
                    length++;
                    nextVal += diff;
                }
            }
            maxLen = max(maxLen, length);
        }
    }
    return maxLen;
}

int main() {
    vector<int> nums = {3,6,9,12};
    cout << longestArithSeqLength(nums) << endl; // Output: 4
    return 0;
}

Line Notes

int n = nums.size();Get size of input vector

int maxLen = n >= 2 ? 2 : n;Initialize max length with minimum valid subsequence length

for (int i = 0; i < n; i++)Outer loop picks first element

for (int j = i + 1; j < n; j++)Inner loop picks second element to define difference

int diff = nums[j] - nums[i];Calculate difference for arithmetic subsequence

int length = 2;Start length count from initial pair

int nextVal = nums[j] + diff;Next expected value in sequence

for (int k = j + 1; k < n; k++)Scan remaining elements for continuation

if (nums[k] == nextVal)Check if current element continues the sequence

length++;Increment length when sequence continues

nextVal += diff;Update next expected value

maxLen = max(maxLen, length);Update global max length

return maxLen;Return final answer

function longestArithSeqLength(nums) {
    const n = nums.length;
    let maxLen = n >= 2 ? 2 : n;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            const diff = nums[j] - nums[i];
            let length = 2;
            let nextVal = nums[j] + diff;
            for (let k = j + 1; k < n; k++) {
                if (nums[k] === nextVal) {
                    length++;
                    nextVal += diff;
                }
            }
            maxLen = Math.max(maxLen, length);
        }
    }
    return maxLen;
}

// Example usage
console.log(longestArithSeqLength([3,6,9,12])); // Output: 4

Line Notes

const n = nums.length;Get length of input array

let maxLen = n >= 2 ? 2 : n;Initialize max length with minimum valid subsequence length

for (let i = 0; i < n; i++)Outer loop picks first element

for (let j = i + 1; j < n; j++)Inner loop picks second element to define difference

const diff = nums[j] - nums[i];Calculate difference for arithmetic subsequence

let length = 2;Start length count from initial pair

let nextVal = nums[j] + diff;Next expected value in sequence

for (let k = j + 1; k < n; k++)Scan remaining elements for continuation

if (nums[k] === nextVal)Check if current element continues the sequence

length++;Increment length when sequence continues

nextVal += diff;Update next expected value

maxLen = Math.max(maxLen, length);Update global max length

return maxLen;Return final answer

⏱

Complexity

TimeO(n^3)

SpaceO(1)

Three nested loops: first two to pick pairs, third to scan for continuation, leading to cubic time.

💡 For n=20, this means about 8000 operations per inner loop, totaling millions of operations, which is too slow for large inputs.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and verify correctness on small inputs.

🧠

Dynamic Programming with Hash Maps (Tracking Differences)

💡 This approach introduces memoization by storing the length of arithmetic subsequences ending at each index with a given difference, avoiding repeated scanning.

Intuition

For each element, look back at previous elements and update the length of subsequences with the difference between them. Use a hash map to track lengths by difference.

Algorithm

1. Initialize an array of hash maps dp, where dp[i] maps difference to length of arithmetic subsequence ending at i.
2. Iterate over each pair (j, i) with j < i, compute diff = nums[i] - nums[j].
3. Update dp[i][diff] = dp[j].get(diff, 1) + 1, extending the subsequence ending at j.
4. Track the maximum length found during updates.

💡 This approach avoids scanning ahead by building solutions bottom-up and remembering lengths for each difference.

</>

Code

def longestArithSeqLength(nums):
    n = len(nums)
    dp = [dict() for _ in range(n)]
    max_len = 2 if n >= 2 else n
    for i in range(n):
        for j in range(i):
            diff = nums[i] - nums[j]
            length = dp[j].get(diff, 1) + 1
            dp[i][diff] = max(dp[i].get(diff, 0), length)
            max_len = max(max_len, dp[i][diff])
    return max_len

# Example usage
if __name__ == '__main__':
    print(longestArithSeqLength([3,6,9,12]))  # Output: 4

Line Notes

dp = [dict() for _ in range(n)]Create a list of dictionaries to store difference-length mappings per index

max_len = 2 if n >= 2 else nInitialize max length with minimum valid subsequence length

for i in range(n)Iterate over each element as the subsequence end

for j in range(i)Look back at all previous elements to find differences

diff = nums[i] - nums[j]Calculate difference between current and previous element

length = dp[j].get(diff, 1) + 1Extend subsequence length if difference seen before, else start new length 2

dp[i][diff] = max(dp[i].get(diff, 0), length)Update dp for current index and difference with max length

max_len = max(max_len, dp[i][diff])Track global maximum length

return max_lenReturn the longest arithmetic subsequence length found

import java.util.*;
public class Solution {
    public static int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) dp[i] = new HashMap<>();
        int maxLen = n >= 2 ? 2 : n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                int length = dp[j].getOrDefault(diff, 1) + 1;
                dp[i].put(diff, Math.max(dp[i].getOrDefault(diff, 0), length));
                maxLen = Math.max(maxLen, dp[i].get(diff));
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        System.out.println(longestArithSeqLength(new int[]{3,6,9,12})); // Output: 4
    }
}

Line Notes

Map<Integer, Integer>[] dp = new HashMap[n];Array of hash maps to store difference-length pairs per index

for (int i = 0; i < n; i++) dp[i] = new HashMap<>();Initialize each map

int maxLen = n >= 2 ? 2 : n;Initialize max length with minimum valid subsequence length

for (int i = 0; i < n; i++)Iterate over each element as subsequence end

for (int j = 0; j < i; j++)Look back at previous elements

int diff = nums[i] - nums[j];Calculate difference

int length = dp[j].getOrDefault(diff, 1) + 1;Extend subsequence length or start new

dp[i].put(diff, Math.max(dp[i].getOrDefault(diff, 0), length));Update dp with max length for difference

maxLen = Math.max(maxLen, dp[i].get(diff));Update global max length

return maxLen;Return final answer

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int longestArithSeqLength(vector<int>& nums) {
    int n = nums.size();
    vector<unordered_map<int,int>> dp(n);
    int maxLen = n >= 2 ? 2 : n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            int length = dp[j].count(diff) ? dp[j][diff] + 1 : 2;
            dp[i][diff] = max(dp[i][diff], length);
            maxLen = max(maxLen, dp[i][diff]);
        }
    }
    return maxLen;
}

int main() {
    vector<int> nums = {3,6,9,12};
    cout << longestArithSeqLength(nums) << endl; // Output: 4
    return 0;
}

Line Notes

vector<unordered_map<int,int>> dp(n);Vector of hash maps to store difference-length pairs per index

int maxLen = n >= 2 ? 2 : n;Initialize max length with minimum valid subsequence length

for (int i = 0; i < n; i++)Iterate over each element as subsequence end

for (int j = 0; j < i; j++)Look back at previous elements

int diff = nums[i] - nums[j];Calculate difference

int length = dp[j].count(diff) ? dp[j][diff] + 1 : 2;Extend subsequence length or start new length 2

dp[i][diff] = max(dp[i][diff], length);Update dp with max length for difference

maxLen = max(maxLen, dp[i][diff]);Update global max length

return maxLen;Return final answer

function longestArithSeqLength(nums) {
    const n = nums.length;
    const dp = Array.from({length: n}, () => new Map());
    let maxLen = n >= 2 ? 2 : n;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            const length = dp[j].has(diff) ? dp[j].get(diff) + 1 : 2;
            dp[i].set(diff, Math.max(dp[i].get(diff) || 0, length));
            maxLen = Math.max(maxLen, dp[i].get(diff));
        }
    }
    return maxLen;
}

// Example usage
console.log(longestArithSeqLength([3,6,9,12])); // Output: 4

Line Notes

const dp = Array.from({length: n}, () => new Map());Create array of maps to track difference-length pairs per index

let maxLen = n >= 2 ? 2 : n;Initialize max length with minimum valid subsequence length

for (let i = 0; i < n; i++)Iterate over each element as subsequence end

for (let j = 0; j < i; j++)Look back at previous elements

const diff = nums[i] - nums[j];Calculate difference

const length = dp[j].has(diff) ? dp[j].get(diff) + 1 : 2;Extend subsequence length or start new length 2

dp[i].set(diff, Math.max(dp[i].get(diff) || 0, length));Update dp with max length for difference

maxLen = Math.max(maxLen, dp[i].get(diff));Update global max length

return maxLen;Return final answer

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Two nested loops for pairs, and each index stores a map of differences which can be up to O(n) in worst case.

💡 For n=1000, about 1 million operations, which is feasible in interviews and production.

Interview Verdict: Accepted

This approach is efficient enough for large inputs and is the standard solution for this problem.

🧠

Optimized DP with Array of Hash Maps and Early Max Tracking

💡 This approach is a refinement of the previous DP method, emphasizing careful max tracking and clean code structure for interview clarity.

Intuition

Use the same DP with hash maps but highlight the importance of updating max length immediately and using concise code to avoid bugs.

Algorithm

1. Create an array dp of hash maps to store difference to subsequence length mappings.
2. For each pair (j, i), compute difference and update dp[i][diff] based on dp[j][diff].
3. Update the global maximum length during each update.
4. Return the maximum length found.

💡 This approach is straightforward once you understand the DP with hash maps; the key is to keep max length updated during iteration.

</>

Code

def longestArithSeqLength(nums):
    n = len(nums)
    dp = [dict() for _ in range(n)]
    max_len = 0
    for i in range(n):
        for j in range(i):
            diff = nums[i] - nums[j]
            prev_len = dp[j].get(diff, 1)
            dp[i][diff] = prev_len + 1
            max_len = max(max_len, dp[i][diff])
    return max_len if max_len > 0 else n

# Example usage
if __name__ == '__main__':
    print(longestArithSeqLength([3,6,9,12]))  # Output: 4

Line Notes

dp = [dict() for _ in range(n)]Initialize dp array of dictionaries for difference-length mappings

max_len = 0Initialize max length to zero to track maximum subsequence length

for i in range(n)Iterate over each element as subsequence end

for j in range(i)Look back at previous elements

diff = nums[i] - nums[j]Calculate difference

prev_len = dp[j].get(diff, 1)Get previous subsequence length or start new at 1

dp[i][diff] = prev_len + 1Update dp with extended subsequence length

max_len = max(max_len, dp[i][diff])Update global max length

return max_len if max_len > 0 else nReturn max length or n if no subsequence found

import java.util.*;
public class Solution {
    public static int longestArithSeqLength(int[] nums) {
        int n = nums.length;
        Map<Integer, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) dp[i] = new HashMap<>();
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                int diff = nums[i] - nums[j];
                int prevLen = dp[j].getOrDefault(diff, 1);
                dp[i].put(diff, prevLen + 1);
                maxLen = Math.max(maxLen, dp[i].get(diff));
            }
        }
        return maxLen > 0 ? maxLen : n;
    }

    public static void main(String[] args) {
        System.out.println(longestArithSeqLength(new int[]{3,6,9,12})); // Output: 4
    }
}

Line Notes

Map<Integer, Integer>[] dp = new HashMap[n];Initialize array of hash maps for difference-length pairs

int maxLen = 0;Initialize max length to zero

for (int i = 0; i < n; i++)Iterate over each element as subsequence end

for (int j = 0; j < i; j++)Look back at previous elements

int diff = nums[i] - nums[j];Calculate difference

int prevLen = dp[j].getOrDefault(diff, 1);Get previous subsequence length or start new

dp[i].put(diff, prevLen + 1);Update dp with extended subsequence length

maxLen = Math.max(maxLen, dp[i].get(diff));Update global max length

return maxLen > 0 ? maxLen : n;Return max length or n if no subsequence found

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

int longestArithSeqLength(vector<int>& nums) {
    int n = nums.size();
    vector<unordered_map<int,int>> dp(n);
    int maxLen = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            int diff = nums[i] - nums[j];
            int prevLen = dp[j].count(diff) ? dp[j][diff] : 1;
            dp[i][diff] = prevLen + 1;
            maxLen = max(maxLen, dp[i][diff]);
        }
    }
    return maxLen > 0 ? maxLen : n;
}

int main() {
    vector<int> nums = {3,6,9,12};
    cout << longestArithSeqLength(nums) << endl; // Output: 4
    return 0;
}

Line Notes

vector<unordered_map<int,int>> dp(n);Initialize vector of hash maps for difference-length pairs

int maxLen = 0;Initialize max length to zero

for (int i = 0; i < n; i++)Iterate over each element as subsequence end

for (int j = 0; j < i; j++)Look back at previous elements

int diff = nums[i] - nums[j];Calculate difference

int prevLen = dp[j].count(diff) ? dp[j][diff] : 1;Get previous subsequence length or start new

dp[i][diff] = prevLen + 1;Update dp with extended subsequence length

maxLen = max(maxLen, dp[i][diff]);Update global max length

return maxLen > 0 ? maxLen : n;Return max length or n if no subsequence found

function longestArithSeqLength(nums) {
    const n = nums.length;
    const dp = Array.from({length: n}, () => new Map());
    let maxLen = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            const diff = nums[i] - nums[j];
            const prevLen = dp[j].get(diff) || 1;
            dp[i].set(diff, prevLen + 1);
            maxLen = Math.max(maxLen, dp[i].get(diff));
        }
    }
    return maxLen > 0 ? maxLen : n;
}

// Example usage
console.log(longestArithSeqLength([3,6,9,12])); // Output: 4

Line Notes

const dp = Array.from({length: n}, () => new Map());Initialize array of maps for difference-length pairs

let maxLen = 0;Initialize max length to zero

for (let i = 0; i < n; i++)Iterate over each element as subsequence end

for (let j = 0; j < i; j++)Look back at previous elements

const diff = nums[i] - nums[j];Calculate difference

const prevLen = dp[j].get(diff) || 1;Get previous subsequence length or start new

dp[i].set(diff, prevLen + 1);Update dp with extended subsequence length

maxLen = Math.max(maxLen, dp[i].get(diff));Update global max length

return maxLen > 0 ? maxLen : n;Return max length or n if no subsequence found

⏱

Complexity

TimeO(n^2)

SpaceO(n^2)

Same as previous DP approach but with cleaner max tracking.

💡 This is the recommended approach to implement in interviews for clarity and efficiency.

Interview Verdict: Accepted

This is the polished and preferred solution for interviews and production.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, you should mention brute force to show understanding but implement the DP with hash maps approach for efficiency and clarity.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^3)	O(1)	No	No	Mention only - never code
2. DP with Hash Maps	O(n^2)	O(n^2)	No	Yes, with extra bookkeeping	Code this approach
3. Optimized DP with Early Max Tracking	O(n^2)	O(n^2)	No	Yes	Preferred polished solution

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying the problem, then explain brute force to show understanding, and finally present the optimized DP solution with hash maps.

How to Present

Clarify the problem and constraints with the interviewer.Explain the brute force approach to show understanding of the problem.Discuss why brute force is inefficient and introduce the DP with hash maps approach.Write clean, optimized DP code and explain how it tracks subsequence lengths by difference.Test your code with sample inputs and edge cases.

Time Allocation

Clarify: 3min → Approach: 5min → Code: 10min → Test: 5min. Total ~23min

What the Interviewer Tests

The interviewer tests your ability to identify the key insight of tracking subsequence lengths by difference, your understanding of hash maps for memoization, and your coding clarity and correctness.

Common Follow-ups

• What if the input array is very large? → Use the DP approach; it's efficient enough for 10^5 elements.
• Can you reconstruct the longest arithmetic subsequence? → Yes, by storing predecessors along with lengths.

💡 These follow-ups test your understanding of scalability and ability to extend solutions to reconstruction problems.

🔍

Pattern Recognition

When to Use

1) Problem asks for longest subsequence with constant difference, 2) Input is an array of integers, 3) You need to track sequences by difference, 4) Constraints allow O(n^2) solution.

Signature Phrases

'longest arithmetic subsequence''difference between consecutive elements is the same'

NOT This Pattern When

Problems asking for longest substring or subarray with no difference constraints are different patterns.

Similar Problems

Longest Arithmetic Subarray - similar but requires contiguous elementsLongest Consecutive Sequence - also uses hash maps but tracks consecutive integersLongest Increasing Subsequence - tracks increasing sequences but not fixed difference

Practice

1. Consider the following Python function implementing the optimal approach for checking if a continuous subarray sum is a multiple of k. What is the return value when called with nums = [5, 0, 0] and k = 3?

easy

A. False

B. Returns True only if k divides the sum of the entire array

C. Raises an error due to modulo by zero

D. True

Solution

1. Step 1: Trace running_sum and remainder_map for each iteration

   i=0: running_sum=5%3=2, remainder_map={0:-1,2:0} i=1: running_sum=2+0=2%3=2, 2 in map at index 0, i-0=1 (not >1), continue i=2: running_sum=2+0=2%3=2, 2 in map at index 0, i-0=2 (>1), return True

2. Step 2: Confirm return value

   Function returns True because subarray [0,0] starting at index 1 has sum 0 which is multiple of 3.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Subarray length check and remainder map usage confirm True [OK]

Hint: Check remainder_map and subarray length > 1 carefully [OK]

Common Mistakes:

• Off-by-one error in subarray length check
• Ignoring initial remainder 0 at index -1
• Modulo by zero confusion when k=0

2. The following code attempts to count the number of subarrays with bounded maximum using the optimal approach, but it contains a subtle bug:

def countAtMost(nums, bound):
    count = 0
    length = 0
    for num in nums:
        if num <= bound:
            length += 1
            count += length
        else:
            # Bug: missing reset of length here
            pass
    return count

def numSubarrayBoundedMax(nums, left, right):
    return countAtMost(nums, right) - countAtMost(nums, left - 1)

What is the bug in this code?

medium

A. The variable 'count' is not reset inside the loop, causing overcounting.

B. The function countAtMost should use max instead of length to track subarray size.

C. The 'length' variable is not reset to zero when encountering a number greater than bound.

D. The subtraction in numSubarrayBoundedMax should be reversed to avoid negative results.

Solution

1. Step 1: Understand the role of 'length'

   'length' tracks the length of the current valid subarray segment where elements ≤ bound.

2. Step 2: Identify the bug

   When an element > bound is encountered, 'length' must reset to 0 to avoid counting invalid subarrays. The code misses this reset, causing overcounting.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Resetting 'length' on invalid elements is essential [OK]

Hint: Reset 'length' to zero on elements > bound [OK]

Common Mistakes:

• Forgetting to reset length
• Incorrect subtraction order
• Misusing count variable

3. Suppose the problem is modified so that elements can be reused multiple times to form pairs whose sums are divisible by k. Which of the following changes to the original frequency map approach correctly handles this variant?

hard

A. Use a dynamic programming approach to count combinations allowing reuse and check divisibility.

B. Use a frequency map but check only if the total number of elements is even, ignoring remainder counts.

C. Use a greedy approach to pair elements as many times as possible without frequency constraints.

D. Keep the frequency map but allow pairing elements with themselves any number of times.

Solution

1. Step 1: Understand reuse changes problem nature

   Allowing reuse means frequency counts no longer limit pairing; pairs can be formed repeatedly from same elements.

2. Step 2: Identify suitable approach

   Frequency map approach relies on fixed counts and fails with reuse. Dynamic programming can track sums with unlimited usage, correctly handling reuse.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   DP handles unlimited reuse and sum divisibility constraints [OK]

Hint: Reuse breaks fixed frequency assumptions; DP needed [OK]

Common Mistakes:

• Assuming frequency map still works unchanged
• Ignoring remainder counts when reuse allowed
• Using greedy without correctness guarantees

4. Suppose the problem is modified so that the input array can contain duplicate numbers and you want to find the length of the longest consecutive sequence considering duplicates as separate elements (e.g., [1,2,2,3] counts as length 4). Which modification to the optimal hash set approach correctly handles this variant?

hard

A. Use a hash map to store counts of each number and sum counts for consecutive numbers to find the longest run.

B. Use the original hash set approach but multiply the length by the count of duplicates for each number.

C. Sort the array and count consecutive runs including duplicates by scanning linearly.

D. Ignore duplicates and apply the original hash set approach since duplicates don't affect sequence length.

Solution

1. Step 1: Understand the variant

   Duplicates count as separate elements, so sequences can include repeated numbers increasing length.

2. Step 2: Evaluate approaches

   Original hash set approach ignores duplicates; multiplying length by counts is incorrect because duplicates may be non-consecutive; sorting and scanning works but is O(n log n).

3. Step 3: Correct approach

   Using a hash map to store counts allows summing counts of consecutive numbers to find the longest run including duplicates efficiently.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash map counting handles duplicates correctly and efficiently [OK]

Hint: Count duplicates explicitly using a hash map [OK]

Common Mistakes:

• Ignoring duplicates
• Multiplying length by counts incorrectly
• Assuming sorting is always best

5. Suppose the input array can contain negative numbers and you want to find the number of subarrays whose sum equals k, but now you want to find the count of subarrays with sum divisible by k instead. Which modification to the optimal prefix sum with hash map approach correctly solves this variant?

hard

A. Use a sliding window approach since divisibility allows shrinking the window easily.

B. Track prefix sums modulo k and count frequencies of each remainder in a hash map.

C. Sort the array and use two pointers to find subarrays with sum divisible by k.

D. Use the original prefix sum approach without changes, as sum equals k and sum divisible by k are equivalent.

Solution

1. Step 1: Understand the problem variant

   We want subarrays where sum % k == 0, not sum == k.

2. Step 2: Modify prefix sums to track remainders

   Compute prefix sums modulo k and count how many prefix sums have the same remainder, since difference of prefix sums with same remainder is divisible by k.

3. Step 3: Use hash map to count frequencies of remainders

   Increment count by frequency of current remainder seen so far.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Sliding window fails with negatives; sorting breaks subarray continuity; original approach doesn't handle divisibility. [OK]

Hint: Use prefix sums modulo k and count remainder frequencies [OK]

Common Mistakes:

• Trying sliding window with negatives
• Ignoring modulo operation
• Assuming sum equals k and divisible by k are same