Getting the longest sequence in 2D Integer array

Question

I've been stuck in this problem for a while. The goal is to return an Arraylist of the longest repetitive sequence. If I have

int[][] a = {{ 1, 1, 3, 4 }
             { 2, 2, 2, 1}
             { 3, 3, 3, 3}
             { 0, 0, 1, 1}};

The method longestSequence() should return an Arraylist of [3,3,3,3] as 3 has the longest sequence. I have to find sequence only horizontally. Please could smb tell me what I did wrong?

   int[][] a = {{ 1, 1, 3, 4 }
                 { 2, 2, 2, 1}
                 { 3, 3, 3, 3}
                 { 0, 0, 1, 1}};

    public List<Integer> longestSequence(int[][]a){
       int count = 1, max = 1;
       List<Integer> list = new ArrayList<Integer>();

       for (int i = 0; i < a.length; i++)
          for(int j = 1; j < a[i].length; j++) {
             if (a[i][j] >= a[i][j-1]) {
                count++;
                list.add(a[i][j]);
             }  else {
                   if (count > max) {
                   max = count;
               }
            list.clear();
            count = 1;
        }
    }

    return list;
}

possible duplicate of Syntax for creating a two-dimensional array — Kumar Saurabh
– Kumar Saurabh, Commented Sep 18, 2015 at 7:20
@KumarSaurabh, the method needs to return the longest sequence, not constuct a 2d array — user4833678
– user4833678, Commented Sep 18, 2015 at 7:24
You're clearing the list after each iteration. You check if the item is >= but you need only =. — TDG
– TDG, Commented Sep 18, 2015 at 7:26
Can you tell us what it does, and explain why that is wrong? — Andy Turner
– Andy Turner, Commented Sep 18, 2015 at 7:27

Andy Turner · Accepted Answer · 2015-09-18 17:25:33Z

2

The problem looks to be that you are not correctly clearing the list, and you aren't keeping the best list as the value to return.

You could keep a maxList, the list of elements corresponding to the run of length max:

max = count; maxList = new ArrayList<>(list);

Don't simply use maxList = list, since that would be cleared by the list.clear() call.

Alternatively, keep the value of the element in the longest run (e.g. 3), and then construct a list at the end of length max where all elements are e.g. 3.

int bestValue = -1;
int bestLength = 0;
for (int i = 0; i < a.length; ++i) {
  int[] row = a[i];
  int j = 0;
  while (j < row.length) {
    int start = j++;
    while (j < row.length && row[j] == row[start]) j++;
    if (j-start > bestLength) {
      bestLength = j - start;
      bestValue = row[start];
    }
  }
}
return Collections.nCopies(bestLength, bestValue);

edited Sep 18, 2015 at 17:25

answered Sep 18, 2015 at 7:30

Andy Turner

141k11 gold badges169 silver badges263 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

user4833678 Over a year ago

So I need two lists? One for max and one temporary list? @AndyTurner

Andy Turner Over a year ago

For your current approach, you need two lists. I've updated the answer with code that avoids creating any lists during the search.

Amr · Accepted Answer · 2015-09-18 20:01:19Z

0

You have a few problems with your implementation. So apart from the 2d dimensional array creation, you keep overriding your result list even if the current seqence is not the maximum one. So to fix this keep a local arrayList to hold the current sequence and only assign it to your result if it's greater than the max.

    int[][] a = {{ 1, 1, 3, 4 },
         { 2, 2, 2, 1},
         { 3, 3, 3, 3},
         { 0, 0, 1, 1}};

    public List<Integer> longestSequence(int[][]a){
       int count = 1, max = 1;
       List<Integer> result = new ArrayList<Integer>();

       for (int i = 0; i < a.length; i++) {
       List<Integer> current = new ArrayList<Integer>();
          for(int j = 1; j < a[i].length; j++) {
             if (a[i][j] >= a[i][j-1]) {
                count++;
                current.add(a[i][j]);
             }  else{
                  if (count > max) {
                  max = count;
                  result = current;
                  }
                 current = new ArrayList<Integer>();
                 count = 1;
             }
           }
        }
      return result ; 
    }

edited Sep 18, 2015 at 20:01

answered Sep 18, 2015 at 7:28

Amr

8124 silver badges15 bronze badges

2 Comments

user4833678 Over a year ago

It's returning an empty List, @Amr

Amr Over a year ago

@John I fixed it now check it again :)

Collectives™ on Stack Overflow

Getting the longest sequence in 2D Integer array

2 Answers 2

2 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related