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](http://stackoverflow.com/questions/12231453/syntax-for-creating-a-two-dimensional-array) — Kumar Saurabh, Sep 18 '15 at 07:20
@KumarSaurabh, the method needs to return the longest sequence, not constuct a 2d array — , Sep 18 '15 at 07:24
You're clearing the list after each iteration. You check if the item is `>=` but you need only `=`. — TDG, Sep 18 '15 at 07:26
Can you tell us what it does, and explain why that is wrong? — Andy Turner, Sep 18 '15 at 07:27

Andy Turner · Answer 1 · 2015-09-18T17:25:33.907

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);

So I need two lists? One for max and one temporary list? @AndyTurner — , Sep 18 '15 at 16:58
For your current approach, you need two lists. I've updated the answer with code that avoids creating any lists during the search. — Andy Turner, Sep 18 '15 at 17:31

Amr · Answer 2 · 2015-09-18T20:01:19.270

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 ; 
    }

@John I fixed it now check it again :) – Amr Sep 18 '15 at 20:01 — Amr, Sep 18 '15 at 20:01

Getting the longest sequence in 2D Integer array

2 Answers2