Ufdjrw

ContourPlot — How do I color by contour curvature?

Should I assume I have passed probation?

Alignment of six matrices

Is there a RAID 0 Equivalent for RAM?

What's the name of the logical fallacy where a debater extends a statement far beyond the original statement to make it true?

"Oh no!" in Latin

Review your own paper in Mathematics

Should I warn a new PhD Student?

Can I say "fingers" when referring to toes?

Sigmoid with a slope but no asymptotes?

How to test the sharpness of a knife?

What is the meaning of "You've never met a graph you didn't like?"

Difference between shutdown options

Did I make a mistake by ccing email to boss to others?

In One Punch Man, is King actually weak?

Origin of pigs as a species

Animation: customize bounce interpolation

How were servants to the Kaiser of Imperial Germany treated and where may I find more information on them

How to I force windows to use a specific version of SQLCMD?

How to write Quadratic equation with negative coefficient

Deciphering cause of death?

Proving an identity involving cross products and coplanar vectors

Why does the Persian emissary display a string of crowned skulls?

Unable to disable Microsoft Store in domain environment

Optimizing this solution: Longest consecutive distinct sequence of integers

I need an alternative to the first fit decreasing bin packing algorithm that always finds an optimal solutionFind an integer not among four billion given onesOptimal sequence to brute force solve a keypad code lockBomb dropping algorithmGenerate a longest bit sequence where all 5-bits consecutive sub sequence are uniqueFind offset sequence in an array of integersfinding longest sequence of consecutive numbersHow to find the longest sequence of consecutive natural successors?Longest sub-sequence the elements of which make up a set of increasing integersAlgorithm: search for incremental sequences of integers from multiple ordered lists

0

Sample input:

5
1
2
1
3
1

First number = # of members in the set, N

Following N numbers = ID's of the members

I'd have to find the size of the longest consecutive sequence of distinct integers in the set. In this instance, it'd be the sequence of 2, 1, 3, so the output would be 3.

My brute force solution would be to generate a sliding window that shrinks in size by 1 every iteration. The initial size is the size of the input. So, for the sample input, it'd evaluate 1, 2, 1, 3, 1 first, if set is not all unique, then decrease the window to 4, and evaluate 1, 2, 1, 3, 2, 1, 3, 1. Keep going until you found a set that's unique.

For one, I believe this algorithm would be O(N^2) time. So, how might I optimize this?

java algorithm data-structures

share|improve this question

asked Mar 7 at 2:45

J. DoeJ. Doe

505

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Your concept of sliding window seems odd. If applying correctly, it should be O(N) instead, the direction is correct so I think you should take a relook at sliding window technique.
  
  – Pham Trung
  Mar 7 at 2:59
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  What do you mean by "Your concept of sliding window seems odd"?
  
  – J. Doe
  Mar 7 at 3:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  It is not done correctly, you better check geeksforgeeks.org/window-sliding-technique.
  
  – Pham Trung
  Mar 7 at 4:05
  

  
  
  
  

add a comment | 

0

Sample input:

5
1
2
1
3
1

First number = # of members in the set, N

Following N numbers = ID's of the members

I'd have to find the size of the longest consecutive sequence of distinct integers in the set. In this instance, it'd be the sequence of 2, 1, 3, so the output would be 3.

My brute force solution would be to generate a sliding window that shrinks in size by 1 every iteration. The initial size is the size of the input. So, for the sample input, it'd evaluate 1, 2, 1, 3, 1 first, if set is not all unique, then decrease the window to 4, and evaluate 1, 2, 1, 3, 2, 1, 3, 1. Keep going until you found a set that's unique.

For one, I believe this algorithm would be O(N^2) time. So, how might I optimize this?

java algorithm data-structures

share|improve this question

asked Mar 7 at 2:45

J. DoeJ. Doe

505

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Your concept of sliding window seems odd. If applying correctly, it should be O(N) instead, the direction is correct so I think you should take a relook at sliding window technique.
  
  – Pham Trung
  Mar 7 at 2:59
  
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  What do you mean by "Your concept of sliding window seems odd"?
  
  – J. Doe
  Mar 7 at 3:21
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  It is not done correctly, you better check geeksforgeeks.org/window-sliding-technique.
  
  – Pham Trung
  Mar 7 at 4:05
  

  
  
  
  

add a comment | 

Sample input:

5
1
2
1
3
1

First number = # of members in the set, N

Following N numbers = ID's of the members

I'd have to find the size of the longest consecutive sequence of distinct integers in the set. In this instance, it'd be the sequence of 2, 1, 3, so the output would be 3.

My brute force solution would be to generate a sliding window that shrinks in size by 1 every iteration. The initial size is the size of the input. So, for the sample input, it'd evaluate 1, 2, 1, 3, 1 first, if set is not all unique, then decrease the window to 4, and evaluate 1, 2, 1, 3, 2, 1, 3, 1. Keep going until you found a set that's unique.

For one, I believe this algorithm would be O(N^2) time. So, how might I optimize this?

java algorithm data-structures

share|improve this question

asked Mar 7 at 2:45

J. DoeJ. Doe

505

5
1
2
1
3
1

share|improve this question

asked Mar 7 at 2:45

J. DoeJ. Doe

505

share|improve this question

asked Mar 7 at 2:45

J. DoeJ. Doe

505

asked Mar 7 at 2:45

J. DoeJ. Doe

505

asked Mar 7 at 2:45

J. DoeJ. Doe

505

1 Answer
1

active

oldest

votes

2

You can use a hash table for an O(N) solution. Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating.

For sake of completeness here is a straightforward and (hopefully) well commented python implementation:

def longestDistinctSequence(iterable):

 res = 0
 # store the indices of each unique element
 hashmap = 
 # keep track of how back you can go before you run into a repetition
 last_repeat = 0

 # loop through each index and item
 for index, item in enumerate(iterable):

 # how back you can go before you can run into a repetition is the max of:
 # 1. The last occurence of this element (zero if this is first instance)
 # 2. The last_repeat of the last iteration
 last_repeat = max(hashmap.get(item, 0), last_repeat)

 # calculate the global maximum
 res = max(res, index - last_repeat + 1)

 # update the hashmap to reflect the repetition of this element
 hashmap[item] = index + 1

 return res

share|improve this answer

edited Mar 7 at 3:20

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Consider adding <!-- language: lang-python --> above your code, so that it'll be formatted as python.
  
  – Dillon Davis
  Mar 7 at 3:19
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  @DillonDavis whoa that's a thing?!?!? Edited and thanks :)
  
  – Primusa
  Mar 7 at 3:21
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Also, not that its particularly better or worse, but Python provides defaultdict in the collections module as a replacement for dict when you need the behavior hashmap.get(item, 0) achieves.
  
  – Dillon Davis
  Mar 7 at 3:30
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  @DillonDavis thanks for the suggestion! I think .get() is just a little more readable than defaultdict(int) especially when OP seems to be a java person.
  
  – Primusa
  Mar 7 at 3:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Hi, I would like a little bit of clarification. "Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating." Can you elaborate on the reasoning behind this a little?
  
  – J. Doe
  Mar 7 at 7:32
  

  
  
  
  

 | 
show 4 more comments

Your Answer

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);

Sign up using Google

Sign up using Facebook

Sign up using Email and Password

Post as a guest

Name

Email

Required, but never shown

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55035254%2foptimizing-this-solution-longest-consecutive-distinct-sequence-of-integers%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

2

You can use a hash table for an O(N) solution. Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating.

For sake of completeness here is a straightforward and (hopefully) well commented python implementation:

def longestDistinctSequence(iterable):

 res = 0
 # store the indices of each unique element
 hashmap = 
 # keep track of how back you can go before you run into a repetition
 last_repeat = 0

 # loop through each index and item
 for index, item in enumerate(iterable):

 # how back you can go before you can run into a repetition is the max of:
 # 1. The last occurence of this element (zero if this is first instance)
 # 2. The last_repeat of the last iteration
 last_repeat = max(hashmap.get(item, 0), last_repeat)

 # calculate the global maximum
 res = max(res, index - last_repeat + 1)

 # update the hashmap to reflect the repetition of this element
 hashmap[item] = index + 1

 return res

share|improve this answer

edited Mar 7 at 3:20

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Consider adding <!-- language: lang-python --> above your code, so that it'll be formatted as python.
  
  – Dillon Davis
  Mar 7 at 3:19
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  @DillonDavis whoa that's a thing?!?!? Edited and thanks :)
  
  – Primusa
  Mar 7 at 3:21
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Also, not that its particularly better or worse, but Python provides defaultdict in the collections module as a replacement for dict when you need the behavior hashmap.get(item, 0) achieves.
  
  – Dillon Davis
  Mar 7 at 3:30
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  @DillonDavis thanks for the suggestion! I think .get() is just a little more readable than defaultdict(int) especially when OP seems to be a java person.
  
  – Primusa
  Mar 7 at 3:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Hi, I would like a little bit of clarification. "Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating." Can you elaborate on the reasoning behind this a little?
  
  – J. Doe
  Mar 7 at 7:32
  

  
  
  
  

 | 
show 4 more comments

2

You can use a hash table for an O(N) solution. Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating.

For sake of completeness here is a straightforward and (hopefully) well commented python implementation:

def longestDistinctSequence(iterable):

 res = 0
 # store the indices of each unique element
 hashmap = 
 # keep track of how back you can go before you run into a repetition
 last_repeat = 0

 # loop through each index and item
 for index, item in enumerate(iterable):

 # how back you can go before you can run into a repetition is the max of:
 # 1. The last occurence of this element (zero if this is first instance)
 # 2. The last_repeat of the last iteration
 last_repeat = max(hashmap.get(item, 0), last_repeat)

 # calculate the global maximum
 res = max(res, index - last_repeat + 1)

 # update the hashmap to reflect the repetition of this element
 hashmap[item] = index + 1

 return res

share|improve this answer

edited Mar 7 at 3:20

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032

• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Consider adding <!-- language: lang-python --> above your code, so that it'll be formatted as python.
  
  – Dillon Davis
  Mar 7 at 3:19
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  @DillonDavis whoa that's a thing?!?!? Edited and thanks :)
  
  – Primusa
  Mar 7 at 3:21
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  Also, not that its particularly better or worse, but Python provides defaultdict in the collections module as a replacement for dict when you need the behavior hashmap.get(item, 0) achieves.
  
  – Dillon Davis
  Mar 7 at 3:30
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  
  @DillonDavis thanks for the suggestion! I think .get() is just a little more readable than defaultdict(int) especially when OP seems to be a java person.
  
  – Primusa
  Mar 7 at 3:32
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  
  Hi, I would like a little bit of clarification. "Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating." Can you elaborate on the reasoning behind this a little?
  
  – J. Doe
  Mar 7 at 7:32
  

  
  
  
  

 | 
show 4 more comments

You can use a hash table for an O(N) solution. Simply put, keep track of the last index of each unique element and the last time a repetition happens. The maximum between these two variables at each index is how far back you can go at that index without repeating.

For sake of completeness here is a straightforward and (hopefully) well commented python implementation:

def longestDistinctSequence(iterable):

 res = 0
 # store the indices of each unique element
 hashmap = 
 # keep track of how back you can go before you run into a repetition
 last_repeat = 0

 # loop through each index and item
 for index, item in enumerate(iterable):

 # how back you can go before you can run into a repetition is the max of:
 # 1. The last occurence of this element (zero if this is first instance)
 # 2. The last_repeat of the last iteration
 last_repeat = max(hashmap.get(item, 0), last_repeat)

 # calculate the global maximum
 res = max(res, index - last_repeat + 1)

 # update the hashmap to reflect the repetition of this element
 hashmap[item] = index + 1

 return res

share|improve this answer

edited Mar 7 at 3:20

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032

def longestDistinctSequence(iterable):

 res = 0
 # store the indices of each unique element
 hashmap = 
 # keep track of how back you can go before you run into a repetition
 last_repeat = 0

 # loop through each index and item
 for index, item in enumerate(iterable):

 # how back you can go before you can run into a repetition is the max of:
 # 1. The last occurence of this element (zero if this is first instance)
 # 2. The last_repeat of the last iteration
 last_repeat = max(hashmap.get(item, 0), last_repeat)

 # calculate the global maximum
 res = max(res, index - last_repeat + 1)

 # update the hashmap to reflect the repetition of this element
 hashmap[item] = index + 1

 return res

share|improve this answer

edited Mar 7 at 3:20

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032

answered Mar 7 at 3:18

PrimusaPrimusa

8,01021032