Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>You could have two tables:</p> <ul> <li>Start table: (start-point, length)</li> <li>End table: (ending-point, length)</li> </ul> <p>When adding a new item, you would check:</p> <ul> <li>Does value + 1 exist in start table? If so, delete it and create a new entry of (value, length + 1) where length is the "current" length. You'd also update the end table with the same end point but greater length.</li> <li>Does value - 1 exist in the end table? If so, delete it and create a new entry of (value, length + 1), and this time update the start table (the starting position will be the same, but the length will be increased)</li> </ul> <p>If <em>both</em> conditions hold, then you're effectively stitching two existing sequences together - replace the four existing entries with two new entries, representing the single longer sequence.</p> <p>If <em>neither</em> condition holds, you just create a new entry of length 1 in both tables.</p> <p>After all the values have been added, you can just iterate over the start table to find the key with the largest value.</p> <p>I <em>think</em> this would work, and would be O(n) if we assume O(1) hash lookup/add/delete.</p> <p>EDIT: C# implementation. It took a little while to get right, but I think it works :)</p> <pre class="lang-cs prettyprint-override"><code>using System; using System.Collections.Generic; class Test { static void Main(string[] args) { int[] input = {10,21,45,22,7,2,67,19,13,45,12, 11,18,16,17,100,201,20,101}; Dictionary&lt;int, int&gt; starts = new Dictionary&lt;int, int&gt;(); Dictionary&lt;int, int&gt; ends = new Dictionary&lt;int, int&gt;(); foreach (var value in input) { int startLength; int endLength; bool extendsStart = starts.TryGetValue(value + 1, out startLength); bool extendsEnd = ends.TryGetValue(value - 1, out endLength); // Stitch together two sequences if (extendsStart &amp;&amp; extendsEnd) { ends.Remove(value + 1); starts.Remove(value - 1); int start = value - endLength; int newLength = startLength + endLength + 1; starts[start] = newLength; ends[start + newLength - 1] = newLength; } // Value just comes before an existing sequence else if (extendsStart) { int newLength = startLength + 1; starts[value] = newLength; ends[value + newLength - 1] = newLength; starts.Remove(value + 1); } else if (extendsEnd) { int newLength = endLength + 1; starts[value - newLength + 1] = newLength; ends[value] = newLength; ends.Remove(value - 1); } else { starts[value] = 1; ends[value] = 1; } } // Just for diagnostics - could actually pick the longest // in O(n) foreach (var sequence in starts) { Console.WriteLine("Start: {0}; Length: {1}", sequence.Key, sequence.Value); } } } </code></pre> <hr> <p>EDIT: Here's the single-hashset answer implemented in C# too - I agree, it's simpler than the above, but I'm leaving my original answer for posterity:</p> <pre class="lang-cs prettyprint-override"><code>using System; using System.Collections.Generic; using System.Linq; class Test { static void Main(string[] args) { int[] input = {10,21,45,22,7,2,67,19,13,45,12, 11,18,16,17,100,201,20,101}; HashSet&lt;int&gt; values = new HashSet&lt;int&gt;(input); int bestLength = 0; int bestStart = 0; // Can't use foreach as we're modifying it in-place while (values.Count &gt; 0) { int value = values.First(); values.Remove(value); int start = value; while (values.Remove(start - 1)) { start--; } int end = value; while (values.Remove(end + 1)) { end++; } int length = end - start + 1; if (length &gt; bestLength) { bestLength = length; bestStart = start; } } Console.WriteLine("Best sequence starts at {0}; length {1}", bestStart, bestLength); } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. POLongest Consecutive Sequence in an Unsorted Array
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USJon Skeet
    1. USJon Skeet
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COThanks @Jon ! However I have a doubt that if we desire O(1) complexity for our hash lookups wouldn't that mean that our hash buckets will consume memory ? Let's say we have a million numbers in the array and we need to perform this algorithm over it.
      singulars
      1. PO
      1. USAnoop Menon
    2. CO@Anoop: It would probably still be amortized O(1), but it would indeed take quite a lot of memory. I confess the details of hash table implementations are somewhat beyond me, but so long as there aren't hash *collisions* I believe it should be okay. I could be mistaken, of course. I doubt that you'll find any solutions based on hash tables which *don't* rely on O(1) hash operations.
      singulars
      1. PO
      1. USJon Skeet
    3. COWouldn't this algorithm output {start 16, length 3} for the array given in the question? ...which is how I actually understood the question, too. But it seems there are elements allowed within the consecutive list that are not part of the consecutive list.
      singulars
      1. PO
      1. USDaveFar
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload