Use bitwise hashmap.
On Thu, Jan 30, 2014 at 8:46 PM, Don dondod...@gmail.com wrote:
No. If you start at any number in a sequence it will find the entire
sequence. There is no need to start again at some other number in that
sequence.
Don
On Wednesday, January 29, 2014 12:19:21 AM
No. If you start at any number in a sequence it will find the entire
sequence. There is no need to start again at some other number in that
sequence.
Don
On Wednesday, January 29, 2014 12:19:21 AM UTC-5, Varun Sachdeva wrote:
If we don't process the same number more than once, does it not
If we don't process the same number more than once, does it not create a
situation when we miss out on the solution?
For example the digit 6 in this sequence:
1,2,3,4,0,2,3,1,4,5,2,4,3,4,5,6,7,8,9
Varun
Varun Sachdeva
On 28 January 2014 00:29, Don dondod...@gmail.com wrote:
This works, and
Map of STL takes logarithmic time for insertion. Complexity of this
approach reduces to the complexity of sorting. We are still stuck at O(n
log n).
We don't have space to store 10^6 ints or bools. With this memory
constraint I think O(n log n) is the best solution. Please prove me wrong.
On
Given an array of positive numbers arranged in any order. You have to find
the length of longest continuos(difference of +1, -1) sequence in the array.
for eg.
A[] = *5*, 20, 45, *3*, 98, *4*, 21, *1*, 99, *2*
then longest continuos subsequence is [1, 2, 3, 4, 5] and hence the output
should be
I think this the most optimized code i have writen :
#include iostream
#include vector
#include map
using namespace std;
int longest_sequence(vectorint nums) {
mapint,bool mp;
int count;
int max = -;
int n = 0;
for(unsigned int i = 0; i nums.size(); i++) {
mp[nums[i]] = true;
This works, and I think is O(N*log(N)) which is similar to sorting and
scanning.
An unordered map will be faster, in general. It could be made faster in
most cases by looping over items left in the map, to avoid processing the
same number more than once. Also, when the number of items left in
