Longest Arithmetic Subsequence of Given Difference

Problem Description

Ah, the “Longest Arithmetic Subsequence of Given Difference” problem! It’s like trying to find the longest line at a coffee shop, but instead of caffeine, you’re hunting for a sequence of numbers that have a consistent difference. Imagine you’re at a party, and everyone is dancing in a line, but only those who can keep a steady rhythm (or difference) can stay in the line. If someone breaks the rhythm, they’re out!

In simpler terms, given an array of integers and a specific difference, your task is to find the longest subsequence where the difference between consecutive elements is constant. It’s like trying to keep your friends in sync while playing a game of hopscotch, but with numbers instead of chalk.

Code Solution


class Solution {
 public:
  int longestSubsequence(vector& arr, int difference) {
    int ans = 0;
    unordered_map lengthAt;

    for (const int a : arr) {
      if (const auto it = lengthAt.find(a - difference); it != lengthAt.cend())
        lengthAt[a] = it->second + 1;
      else
        lengthAt[a] = 1;
      ans = max(ans, lengthAt[a]);
    }

    return ans;
  }
};

Approach Explanation

The code uses a hash map to keep track of the length of the longest subsequence ending at each number. For each number in the array, it checks if there exists a number that is difference less than the current number. If it does, it extends the subsequence; if not, it starts a new one. This way, it efficiently builds the longest subsequence while traversing the array just once.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(n)

Real-World Example

Imagine you’re a teacher trying to organize students in a line based on their heights, but you want them to maintain a specific height difference. If a student is 5 feet tall, and you want a difference of 1 foot, the next student should be either 4 or 6 feet tall. The longest line of students you can form with this height difference is your answer!