CODEWITHSUNDEEP
javaalgorithm
Learner
Learner

Reputation: 21445

Find the biggest gap after removing a list of rows and columns in an array

I have an array of size m rows n columns with each cell size is considered as 1x1.

Now I am removing a list of rows and columns from this array, next I want to know the biggest gap that can be formed after removing them.

Example:

Array of size 4 rows and 3 columns, now I am removing rows {1,2,3} and columns {1,2}

This results is an array having biggest gap of 12 cells.

Another Example:

  Array of size 4 rows and 4 columns, now I am removing rows {2} and columns {2}

This results is an array having biggest gap of 4 cells.

I have come up with below code that works for this example:

static long process(int n, int m, int[] h, int[] v) {
    ArrayList<ArrayList<Long>> array = new ArrayList<ArrayList<Long>>();
    for (int r = 0; r <= n; r++) {
        ArrayList<Long> temp = new ArrayList<Long>();
        for (int c = 0; c <= m; c++) {
            temp.add((long) 1);
        }
        array.add(temp);
    }

    int[] x = h;
    int xnum = x.length;
    Arrays.sort(x);
    int[] y = v;
    int ynum = y.length;
    Arrays.sort(y);

    // removing bar i means that list at i-1 and at i
    for (int a = xnum - 1; a >= 0; a--) {
        int i = x[a];
        for (int cell = 0; cell < array.get(i).size(); cell++) {
            array.get(i).set(cell, array.get(i).get(cell) + array.get(i - 1).get(cell));
        }
        array.remove(i - 1);
    }

    ArrayList<ArrayList<Long>> newarray = new ArrayList<ArrayList<Long>>();

    for (int col = 0; col < array.get(0).size(); col++) {
        ArrayList<Long> temp = new ArrayList<Long>();
        for (int row = 0; row < array.size(); row++) {
            temp.add(array.get(row).get(col));
        }
        newarray.add(temp);
    }

    for (int b = ynum - 1; b >= 0; b--) {
        int i = y[b];
        for (int cell = 0; cell < newarray.get(i).size(); cell++) {
            newarray.get(i).set(cell, newarray.get(i).get(cell) + newarray.get(i - 1).get(cell));
        }
        newarray.remove(i - 1);
    }

    long max = 1;
    for (ArrayList<Long> arr : newarray) {
        for (long num : arr) {
            if (num > max)
                max = num;
        }
    }
    return max;
}

How can we reduce the time complexity of this code, because the size of rows and columns is:

1 <= rows, columns <= 100000

Upvotes: 0

Views: 576

Answers (1)

Iłya Bursov
Iłya Bursov

Reputation: 24229

Let's start by looking at your current solution, by using simple array instead of ArrayList we can reduce this code to:

static long process(int rows, int cols, int[] hor, int[] ver) {
    final long[][] a = new long[rows][cols];
    for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) a[i][j] = 1;

    for (int h : hor) for (int j = 0; j < cols; j++) a[h - 1][j] = a[h][j] = a[h - 1][j] + a[h][j];
    for (int v : ver) for (int i = 0; i < rows; i++) a[i][v - 1] = a[i][v] = a[i][v - 1] + a[i][v];

    long max = 0;
    for (int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) max = Math.max(max, a[i][j]);
    return max;
}

this code has complexity O(N^2)

but, we should understand that biggest gap will be in place where biggest count of consecutive rows and columns are removed, thus we can simplify algorithm to:

static int maxConsecutive(int[] a) {
    Arrays.sort(a);

    int max = 0;
    int start = 0;
    for (int i = 0; i < a.length; i++)
        if (a[i] - a[start] == i - start) max = Math.max(max, i - start + 1);
        else start = i;

    return max;
}

static long process(int rows, int cols, int[] hor, int[] ver) {
    long maxH = maxConsecutive(hor);
    long maxV = maxConsecutive(ver);
    return (maxH + 1) * (maxV + 1);
}

which has complexity O(logN)

Upvotes: 2

Related Questions