I want to maximum number of consecutive elements greater than or equal to given element

Question

I was solving a problem, in it i have to return maximum number of times consecutively elements were greater(and equal) or lesser than the given element in an list. For example :- Consider a list of elements [5,10,8,9] and element = 8 Here there are 3 consecutive elements which are greater(and equal) than 8 i.e. 10,8,9 so i return 3.

Another Example:-

Consider a list of elements [5,10,8,9,1,2,3,4,5,8,9] and element =8 Here there are 3 consecutive elements which are greater(or equal) than 8 i.e 10,8,9 but after it there are 5 consecutive elements which are lesser than 8 i.e 1,2,3,4,5 so maximum of them is 5 so i return 5.

I tried the below Code, but i was not getting right answer.

What i did was iterate through the list and see if the element is greater than the given element if it is i increment and i do it till i receive an element which is lesser, if i receive element lesser i add the counter to set and make it zero. Similarly for lower elements. and finally i tried to return the maximum of the elements. But i do not how it is not working, all the elements that i am adding are not getting added in the set.

 public static int findLongest(List<Integer> hours, int limit) {

      int longWork = 0;

      int shortWork = 0;

      Set<Integer> hash_set = new HashSet<Integer>();
      for(int i=0 ; i<hours.size() ; i++) {
          if(hours.get(i) >= limit) {
              longWork++ ;
              hash_set.add(shortWork);
              shortWork = 0;
          }
          else if(hours.get(i) < limit) {
              shortWork++ ;
              hash_set.add(longWork);
              longWork = 0;
          }

      }

      int finalAns = Collections.max(hash_set);
      return finalAns ;

  }
}

Answer 1

This also checks that the numbers that are smaller or greater are consecutive. Maybe not the most efficient, but it works.

public static int findLongest(List<Integer> hours, int limit) {
    int longWork = 0;
    int shortWork = 0;
    Set<Integer> hash_set = new HashSet<>();

    Collections.sort(hours);
    int value;

    for(int i = 0; i< hours.size(); i++){
        value = hours.get(i);
        if(hours.size()- 1 == i){
            if((hours.get(hours.size() - 1) == hours.get(i - 1) + 1) && hours.get(i) >= limit){
                longWork++;
                hash_set.add(longWork);
                break;
            }
            break;

        }else{
            if((value + 1) == hours.get(i + 1) && hours.get(i) >= limit){
                longWork++;
            }else {
                longWork++;
                hash_set.add(longWork);
                longWork = 0;
            }
        }

    }

    for(int i = 0; i< hours.size(); i++){

        value = hours.get(i);

        if(hours.size()- 1 == i){
            if((hours.get(hours.size()- 1) == hours.get(i - 1) + 1) && hours.get(i) <= limit){
                shortWork++;
                hash_set.add(shortWork);
                break;
            }
            break;

        }else{
            if((value + 1) == hours.get(i + 1) && hours.get(i) <= limit){
                shortWork++;
            }else {
                shortWork++;
                hash_set.add(shortWork);
                shortWork = 0;
            }
        }
    }

    int finalAns = Collections.max(hash_set);
    return finalAns;

}

Answer 2

This problem can be reduced to the standard known problem of Maximum consecutive one’s (or zeros) in a binary array. Elements which are greater than or equal to the limit can be represented as 1 and the elements which are smaller than limit can be represented as 0. So for the following example:

[5,10,8,9] and element = 8

the problem reduces to

Finding the maximum consecutive one’s (or zeros) in binary array [0,1,1,1].

Answer 3

The problem is that you add the wrong value to your HashSet. When increasing longWork you need to add longWork instead of shortWork like this:

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(new Integer[] {5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9});
    List<Integer> list2 = Arrays.asList(new Integer[] {5, 10, 8, 9});
    List<Integer> list3 = Arrays.asList(new Integer[] {5, 10, 6, 8, 4, 9});
    System.out.println(list1 + " -> " + findLongest(list1, 8));
    System.out.println(list2 + " -> " + findLongest(list2, 8));
    System.out.println(list3 + " -> " + findLongest(list3, 8));
}

public static int findLongest(List<Integer> hours, int limit) {
    int longWork = 0;
    int shortWork = 0;

    Set<Integer> hash_set = new HashSet<Integer>();
    for (int i = 0; i < hours.size(); i++) {
        if (hours.get(i) >= limit) {
            longWork++;
            hash_set.add(longWork);
            shortWork = 0;
        }
        else if (hours.get(i) < limit) {
            shortWork++;
            hash_set.add(shortWork);
            longWork = 0;
        }
    }
    int finalAns = Collections.max(hash_set);
    return finalAns;
}

Then the output is:

[5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9] -> 5
[5, 10, 8, 9] -> 3
[5, 10, 6, 8, 4, 9] -> 1

Edit: Or (like mentioned in the comments) you can just add the final values after the loop, to make shure the last values are added, although there is no other number anymore (like in the second list: the value of longWork is 3, but it's never added because there is no value that is smaller after the list of greater values).

So this will also work:

public static void main(String[] args) {
    List<Integer> list1 = Arrays.asList(new Integer[] {5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9});
    List<Integer> list2 = Arrays.asList(new Integer[] {5, 10, 8, 9});
    List<Integer> list3 = Arrays.asList(new Integer[] {5, 10, 6, 8, 4, 9});
    System.out.println(list1 + " -> " + findLongest(list1, 8));
    System.out.println(list2 + " -> " + findLongest(list2, 8));
    System.out.println(list3 + " -> " + findLongest(list3, 8));
}

public static int findLongest(List<Integer> hours, int limit) {
    int longWork = 0;
    int shortWork = 0;

    Set<Integer> hash_set = new HashSet<Integer>();
    for (int i = 0; i < hours.size(); i++) {
        if (hours.get(i) >= limit) {
            longWork++;
            hash_set.add(shortWork);
            shortWork = 0;
        }
        else if (hours.get(i) < limit) {
            shortWork++;
            hash_set.add(longWork);
            longWork = 0;
        }
    }
    //add the last values
    hash_set.add(shortWork);
    hash_set.add(longWork);

    int finalAns = Collections.max(hash_set);
    return finalAns;
}

The output again is:

[5, 10, 8, 9, 1, 2, 3, 4, 5, 8, 9] -> 5
[5, 10, 8, 9] -> 3
[5, 10, 6, 8, 4, 9] -> 1

Answer 4

The problem with this implementation is that you don't handle the last run: you don't add the final values of longWork and shortWork after the loop. (This also means that you would get an exception for an empty input).

Try adding them both to the set after the loop, before you call Collections.max.

---

However, there is no need for the set here. You are just looking for the longest run, so all you need to do is keep the longest run length.

int longest = 0;
int a = 0;
while (a < hours.length()) {
  // Start of this run.
  int start = a;
  // Value of discriminator in this run.
  boolean ge = hours.get(a) >= limit;

  // Increment the pointer until you hit the end,
  // or you find the first element of the next run.
  do {
    ++a;
  } while (a < hours.length()
     && (hours.get(a) >= limit) == ge);

  // Maybe update the longest.
  longest = max(longest, a - start);
}
return longest;

Answer 5

First of all, your solution is flawed. That single hash set isn't the right data structure to remember the information you need to "remember". And it really doesn't help that you keep pushing values into that set during each loop operation (note that your code does an if/else ... and both, if-then and if-else are pushing a value into the set: that achieves nothing useful).

To really solve your problem, remember what you have to do: you have to identify consecutive sub-lists of your list, either with numbers < X, or >= X.

To solve your problem, you have to walk over your list, and then you need to remember what previously happened:

• if you are within a "sub sequence", then you have to decide if the next element in the list also belongs into that sequence, if so, the current sub sequence gets one more element
• if a "sub sequence" just ended, you should check if that sub sequence has more elements than previous sub sequences