Algorithm for finding consecutive elements from a set

Posted on 2009-12-17
Last Modified: 2012-05-08
I'm trying to write a short function/procedure/algorithm that takes as input a set S of n integers and a positive integer 1 < k <= n and returns true iff there's a subset of S with k consecutive numbers. I'm also trying to find an algorithm that will solve this problem in place, without allocating memory for another data structure for sorting the set. The best I can think of so far is an algorithm that runs in n^2 time, but I'm wondering if it's possible to do better.

I have my code (Java) below, but if anybody could point out any possible time/memory improvements I'd appreciate it. Thanks.
for(Iterator<Integer> iter1 = s.iterator(); iter1.hasNext(); ) {
   int x = 0, b =;
   for(Iterator<Integer> iter2 = s.iterator(); iter2.hasNext(); ) {
      x |= (1 << - b);
   if((1 << k) - 1 == x) {
      return true;
return false;

Open in new window

Question by:tjgquicken
    LVL 39

    Accepted Solution

    For a search like that you're better off doing a sort first.  (you don't need more memory you can sort in place with a Binary Tree Sort:

    From there your search  gets better as you only need to check every kth' element, then do a check in between  (assuming you have a previous as well.)

    If  i is your index:

    if  (S[i] + K-1 != S[i+K-1] )
      // not possible to be consecutive.
    i = i+K-1 ;
    //check in between.

    Efficiency grows as K increases.

    LVL 3

    Expert Comment

    I hope this works =D
    //I have not tested this code, but something of the like should work
    private boolean areConsecutives (int[] s, int k) {
      int prev int; //The previous integer
      int countConsec = 0; //The number of integers in a row
      prev = s[0]
      for (int current = 1; current < s.length; current++) {
        if (prev + 1 == current)) {
          if (countConsec >= k)
            return true;
        } else
          countConsec = 0
      prev = current;

    Open in new window

    LVL 3

    Expert Comment

    oops!  the "prev = current" should be moved up one line--it should be inside of the last brace.
    LVL 31

    Expert Comment

    How about including all your source code?

    From the three solutions (your snippet and two other offerings), it is not clear to me what the requirements are. So, here is an example, and you tell me the expected answer.
    k = 5
    S = {9,2,3,4,8,12,10,11,22,44}

    CASE A: No pre-sorting:
    If we scan S in order of element appearance, then the largest value of consecutive numbers is 3; namely, {2,3,4}; and the test fails to meet the requirement of k=5.

    CASE B: pre-sorting:
    If we sort S, then we get:
    SSort = {2,3,4,8,9,10,11,12,22,44}
    Now, the longest consecutive sequence is {8,9,10,11,12}, whose length is 5; so the test is a success.

    Which scenario are you looking for: CASE A or B?

    Also, could you comment in detail what the following is doing? Maybe a simple numerical example illustrating this would help.

          x |= (1 << - b);       <------- shifting?? bit operations??
       if((1 << k) - 1 == x) {  <------ shifting??
    LVL 31

    Expert Comment

    In the first post:

    if  (S[i] + K-1 != S[i+K-1] )  <-------- There was a mismatch, so agree that not consecutive starting from i
      // not possible to be consecutive.
    i = i+K-1 ;                       <-------- So, how is it that we can skip K-1 elements?

    Suppose k=5 and S = {1,3,4,5,6,7,11,12}
    When i=0, S[0] is 1.
    (S[i] + K-1 != S[i+K-1] ) ---> (1 + 5-1 != S[0+5-1] ) -->  ( 5 != S[4] ) -->  ( 5 != 6 )
    So, i = i+K-1 --> 0 = 0+5-1 --> i = 4; but S[4] = 6; but correct answer has sequence starting at i=1.

    else                               <--------- We have the expected end point so agree that
    //check in between.      <-------- we must make sure consecutive in between
    LVL 39

    Expert Comment

    by:Kyle Abrahams
    phoffric . . . you are correct and thank you for pointing out the error.    

    Does the author need further assistance?

    Featured Post

    How your wiki can always stay up-to-date

    Quip doubles as a “living” wiki and a project management tool that evolves with your organization. As you finish projects in Quip, the work remains, easily accessible to all team members, new and old.
    - Increase transparency
    - Onboard new hires faster
    - Access from mobile/offline

    Join & Write a Comment

    Suggested Solutions

    One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
    Article by: Nadia
    Linear search (searching each index in an array one by one) works almost everywhere but it is not optimal in many cases. Let's assume, we have a book which has 42949672960 pages. We also have a table of contents. Now we want to read the content on p…
    Need more eyes on your posted question? Go ahead and follow the quick steps in this video to learn how to Request Attention to your question. *Log into your Experts Exchange account *Find the question you want to Request Attention for *Go to the e…
    In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

    754 members asked questions and received personalized solutions in the past 7 days.

    Join the community of 500,000 technology professionals and ask your questions.

    Join & Ask a Question

    Need Help in Real-Time?

    Connect with top rated Experts

    24 Experts available now in Live!

    Get 1:1 Help Now