Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried to use union-find to solve this but am unsure if my solution actually works in practice.

I first add every element to a union-find (disjoint-set) data structure. This takes O(n) time. I then iterate through each number in the original list of numbers, and perform find() on each number + D to check if its successor is in the union-find. If it is, then I union() the number with its successor.

While I do this, I store the largest subset in a separate variable, and update it when needed.

What is the catch in my approach? Since union and find operations have an amortized cost of O(1), surely my approach would be O(n)?

Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried using sets to solve this but I can't find a solution faster than $O(n^2)$. For example, I have tried adding all items in the array to a TreeSet. This automatically orders the elements, after which I brute force check all the possible sequences. Am I on the right lines or is there a better approach?

Given a list of distinct numbers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried to use union-find to solve this but am unsure if my solution actually works in practice.

I first add every element to a union-find (disjoint-set) data structure. This takes O(n) time. I then iterate through each number in the original list of numbers, and perform find() on each number + D to check if its successor is in the union-find. If it is, then I union() the number with its successor.

While I do this, I store the largest subset in a separate variable, and update it when needed.

What is the catch in my approach? Since union and find operations have an amortized cost of O(1), surely my approach would be O(n)?

Given a list of distinct positive integers, I am trying to find the largest subset that forms an arithmetic sequence with a given difference D.

For example, given D = 5, with the set of numbers 1, 5, 10, 6, 7, 8, 15, 11 the longest sequence would be 5, 10, 15

I have tried to use union-find to solve this but am unsure if my solution actually works in practice.

I first add every element to a union-find (disjoint-set) data structure. This takes O(n) time. I then iterate through each number in the original list of numbers, and perform find() on each number + D to check if its successor is in the union-find. If it is, then I union() the number with its successor.

While I do this, I store the largest subset in a separate variable, and update it when needed.

What is the catch in my approach? Since union and find operations have an amortized cost of O(1), surely my approach would be O(n)?