Given an int array which might contain duplicates, find the largest subset of it which form a sequence. Ex: {1,6,10,4,7,9,5} then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time ??

Thanks in advance :)

# | User | Rating |
---|---|---|

1 | tourist | 3496 |

2 | Um_nik | 3337 |

3 | Petr | 3298 |

4 | W4yneb0t | 3218 |

5 | Radewoosh | 3216 |

6 | OO0OOO00O0OOO0O0…O | 3188 |

7 | Syloviaely | 3168 |

8 | izrak | 3109 |

9 | anta | 3106 |

10 | fateice | 3099 |

# | User | Contrib. |
---|---|---|

1 | tourist | 184 |

2 | rng_58 | 170 |

3 | csacademy | 165 |

4 | Petr | 158 |

5 | Swistakk | 154 |

6 | lewin | 149 |

7 | Errichto | 147 |

8 | matthew99 | 146 |

9 | adamant | 141 |

9 | Zlobober | 141 |

Given an int array which might contain duplicates, find the largest subset of it which form a sequence. Ex: {1,6,10,4,7,9,5} then ans is 4,5,6,7

Sorting is an obvious solution. Can this be done in O(n) time ??

Thanks in advance :)

↑

↓

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/22/2018 12:05:22 (d1).

Desktop version, switch to mobile version.

User lists

Name |
---|

I have a simple idea, but I am not sure whether this is correct or not.

We can adopt a "hash table" to record the integers that have appeared in the set, i.e., for some integer

N, if it appears in the set, thenhash[N] = 1; otherwisehash[N] = 0. Then, the problem is equivalent to finding out the longest sub-sequence consisting of "1"s. If I were correct, this solution has complexityO(n). However, this approach fails if the maximum integer turns out to be too large, for instance, 10^{9}.It's a good approach :) I have implemented it here......Solution

Your code fails on [1,2,3,5,6,7,4].

On the one hand, using a hash table, we can dfs/bfs and find connected components on the path graph (add an edge for each adjacent elements) to solve the problem in Θ(

n) expected time.On the other hand, on the algebraic decision tree model, your problem cannot be solved in

O(n) time. To see this, take an instance of the set disjointness problem (A,B) and transform it to [3A_{1}, ..., 3A_{n}, 3B_{1}+ 1, ..., 3B_{n}+ 1]. Because the set disjointness problem has lower bound [1], your problem has the same bound.Won't this work Here's a in-place algorithm with O(n) time and O(1) extra-space Given array 'A' of size 'n', the goal is to reorder elements in the given array so that they are in their correct positions i.e. A[i]-min(A) is at A[0] when A[i]==min(A) and A[j]-min(A) is at A[1] if A[j] = min(A)+1 and A[k]-min(A) is at A[2] if A[k] = min(A)+2 ..... so on....

An example with duplicates: {45,50,47,45,50,46,49,48,49} Pass1: max(A) = 50, min(A) = 45 Pass2: modified Array: [45,50,47,45,50,46,49,48,49] //45 already at A[A[0]-min(A)] [45,46,47,45,50,50,49,48,49] //swap 50 & 46 [45,46,47,45,50,50,49,48,49] //47 already at A[47-45] [45,46,47,-Inf,50,50,49,48,49] //A[3] = -Inf since it is a duplicate [45,46,47,-Inf,-Inf,50,49,48,49] [45,46,47,-Inf,-Inf,50,49,48,49] [45,46,47,-Inf,49,50,-Inf,48,49] [45,46,47,48,49,50,-Inf,-Inf,49] [45,46,47,48,49,50,-Inf,-Inf,-Inf] Pass3: return true

//Note : instead of -Inf you can use some other marker such as min(A)-2