solve n*m matrix processing in less time

Question

I want to solve a problem in less time complexity. Here are the details:

Given an n*m matrix, n rows and m columns. Initially, the matrix is empty filled with 0s.

Now I will provide n*m positions sequentially in the form of the array which is a 2D int array, each element of the array indicates a position in the matrix (1-index), and I will fill the matrix position to 1 for the given element positions.

I want to find the minimum position (that is index+1) in the array at which we will have the matrix having 1s in the form of a square of length k,

constraints:

1 ≤ n, m ≤ 750
1 ≤ k ≤ min(n, m)
1 ≤ array[i][0] ≤ n
1 ≤ array[i][1] ≤ m

Here is an example:

n=2, m=3; k=2
array = [[1, 2], [2, 3], [2, 1], [1, 3], [2, 2], [1, 1]]

Answer: 5

Explanation:

Let 0 represent an empty cell and 1 represent a filled cell:

 Cell matrix valid square
 array[1]=(1, 2) 010 No
 000
 
 array[2]=(2, 3) 010 No
 001
 
 array[3]=(2, 1) 010 No
 101 
 
 array[4]=(1, 3) 011 No
 010
 
 array[5]=(2, 2) 011 Yes (x = 1, y = 2)
 111
 
 array[6]=(1, 1) 111 Yes (x = 1, y = 1)
 111

we have k = 2 so we need to get a square of size 2 * 2. Now, at the 5th and 6th position the matrix has a square of size 2 * 2 starting at position (1, 2) at position 5, and two squares at (1, 1) and (1, 2) at position 6, so the position is 5 minutes.

Here is my code:

import java.util.*;
public class Main {
 public static int solve(int n, int m, int k, List<List<Integer>> array) {
 int[][] matrix = new int[n][m];
 for (int idx = 0; idx < array.size(); idx++) {
 // Get the coordinates to paint
 int x = array.get(idx).get(0) - 1; 
 int y = array.get(idx).get(1) - 1; 
 matrix[x][y] = 1;
 // Check if a k x k square exists after this operation
 for (int i = 0; i <= n - k; i++) {
 for (int j = 0; j <= m - k; j++) {
 // Check if the k x k square starting at (i, j)
 boolean valid = true;
 for (int dx = 0; dx < k; dx++) {
 for (int dy = 0; dy < k; dy++) {
 if (matrix[i + dx][j + dy] != 1) {
 valid = false;
 break;
 }
 }
 if (!valid) break;
 }
 if (valid) {
 return idx + 1;
 }
 }
 }
 }
 return -1;
 }
 public static void main(String[] args) {
 case1();
 case2();
 case3();
 }
 public static void case1() {
 int n = 2, m = 3, k = 2;
 List<List<Integer>> paint = Arrays.asList(
 Arrays.asList(1, 2),
 Arrays.asList(2, 3),
 Arrays.asList(2, 1),
 Arrays.asList(1, 3),
 Arrays.asList(2, 2),
 Arrays.asList(1, 1)
 );
 System.out.println(solve(n, m, k, paint)); // Expected: 5
 }
 public static void case2() {
 int n = 3, m = 3, k = 3;
 List<List<Integer>> paint = Arrays.asList(
 Arrays.asList(3, 2),
 Arrays.asList(2, 3),
 Arrays.asList(1, 2),
 Arrays.asList(2, 1),
 Arrays.asList(3, 3),
 Arrays.asList(3, 1),
 Arrays.asList(1, 1),
 Arrays.asList(1, 3),
 Arrays.asList(2, 2)
 );
 System.out.println(solve(n, m, k, paint)); // Expected: 9
 }
 public static void case3() {
 int n = 2, m = 1, k = 1;
 List<List<Integer>> paint = Arrays.asList(
 Arrays.asList(2, 1),
 Arrays.asList(1, 1)
 );
 System.out.println(solve(n, m, k, paint)); // Expected: 1
 }
}

My code works for small inputs, but it is not time efficient.

What is the correct approach to solve this in lower time complexity?

• no comment: Are the n*m positions unique, i.e., will they cover each matrix cell exactly once?
• Peilonrayz: @TorbenPutkonen No. We have a scale rules exception. Please read the time-limit-exceeded tag or the many metas which explain our rules for more information.

Answer 1

Review

Your time complexity from your six nested loops is O((nm)^3). You do have breaks, but they don't help much in worst cases. For example if you use n=m and k=n/2 and the positions are given in lexicographical order:

 public static void case4() {
 int n = 50, m = 50, k = 25;
 List<List<Integer>> paint = new ArrayList<>();
 for (int i=1; i<=n; i++)
 for (int j=1; j<=m; j++)
 paint.add(Arrays.asList(i, j));
 System.out.println(solve(n, m, k, paint)); // Expected: 1225
 }

I ran that and counted with steps++; inside your dy loop. It took 85,295,549 steps. With n=m=100 and k=50, i.e., doubling all, it already took 5,322,729,224 steps. That's 62.4 times more steps. Doubling again led to 336,827,667,199 steps, that's 63.3 times more. Approaching the 2^6=64 you'd expect from O(n^6).

The standard names for the numbers of rows and columns of a matrix are m and n, not n and m. But I assume the problem specification isn't yours but was given, so I'll stick with it.

An O(nm log(nm)) algorithm

Do a binary search over the answer range 1 to nm to find the earliest time where the matrix has a filled k-square. Takes log(nm) binary search steps, and each costs the O(nm) for building the partially filled matrix at that point and for checking it as described next.

Given a partially filled matrix, you can check whether it has a filled k-square in O(nm) time. Use prefix sums: First compute every P[i,j] = sum of submatrix from (1,1) to (i,j). Then compute the sum of every k-square and check whether it's k^2. The sum of the k-square ending at (i,j) is P[i,j] - P[i-k,j] - P[i,j-k] + P[i-k,j-k]. Use a similar calculation to compute the prefix sums in the first place.

Sample results

Output of my below implementation:

Your example
Answer: 5
. # #
# # #
One minute earlier:
. # #
# . #
Random 10x10 with k=2
Answer: 29
. . . . # . . . # .
# . . # # . . . # .
# # # # . . # . # .
# # . . . # . . # #
. . . . # . . # . #
. . . . . # . . . #
. . . . . . . . . .
# . . . . . . . . .
# . . . . . # . # .
. # . . # . # . . .
One minute earlier:
. . . . # . . . # .
# . . # # . . . # .
. # # # . . # . # .
# # . . . # . . # #
. . . . # . . # . #
. . . . . # . . . #
. . . . . . . . . .
# . . . . . . . . .
# . . . . . # . # .
. # . . # . # . . .
Random 300x300
k=1 => Answer=1 took 0.4 seconds
k=300 => Answer=90000 took 0.9 seconds
k=4 => Answer=46087 took 1.2 seconds
k=150 => Answer=89985 took 1.6 seconds

Implementation

Edit: I wrote it in Java after all, see my benchmark answer.

I don't do Java, but here's Python in a style that I hope is understandable anyway (Attempt This Online!):

import random
from bisect import bisect_left
from time import time
def generate_positions():
 global array
 array = [[i, j] for i in range(1, n+1) for j in range(1, m+1)]
 random.shuffle(array)
def partial(idx):
 matrix = [[0] * (m+1) for _ in range(n+1)]
 for i, j in array[:idx+1]:
 matrix[i][j] = 1
 return matrix
def show(idx):
 matrix = partial(idx)
 for row in matrix[1:]:
 print(*('.#'[x] for x in row[1:]))
def check(idx):
 matrix = partial(idx)
 P = [[0] * (m+1) for _ in range(n+1)]
 for i in range(1, n+1):
 for j in range(1, m+1):
 P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + matrix[i][j]
 for i in range(k, n+1):
 for j in range(k, m+1):
 if P[i][j] - P[i-k][j] - P[i][j-k] + P[i-k][j-k] == k**2:
 return True
 return False
def solve():
 return bisect_left(range(n*m), True, key=check)
print('Your example')
n, m = 2, 3
k = 2
array = [[1, 2], [2, 3], [2, 1], [1, 3], [2, 2], [1, 1]]
idx = solve()
print('Answer:', idx + 1)
show(idx)
print('One minute earlier:')
show(idx - 1)
print('\nRandom 10x10 with k=2')
n = m = 10
k = 2
generate_positions()
idx = solve()
print('Answer:', idx + 1)
show(idx)
print('One minute earlier:')
show(idx - 1)
print('\nRandom 300x300')
n = m = 300
generate_positions()
for k in 1, 300, 4, 150:
 t0 = time()
 print(f'{k=} => Answer={solve() + 1} took {time()-t0:.1f} seconds')

Answer 2

You can keep track of how many coordinates each square has already filled and you also know that it will be fully filled when the amount will be equal to k x k. The filledCoordinates array marks the top left corner of the square.

Now you just need to generate all the squares which include the given point, you can do that by decreasing the x and y coordinates of your point by maximum of k - 1 and also checking if the coordinates you get still belong to your constraints.

Then you can just update filledCoordinates and check if it matches your condition.

public static int solve(int n, int m, int k, List<List<Integer>> array) {
 int[][] matrix = new int[n][m];
 int[][] filledCoordinates = new int[n - k + 1][m - k + 1];
 int coordinatesNeeded = k * k;
 
 for (int idx = 0; idx < array.size(); idx++) {
 // Get the coordinates to paint
 int x = array.get(idx).get(0) - 1; 
 int y = array.get(idx).get(1) - 1; 
 matrix[x][y] = 1;
 
 int startX = Math.max(0, x - k + 1);
 int endX = Math.min(n - k, x);
 int startY = Math.max(0, y - k + 1);
 int endY = Math.min(m - k, y);
 for (int i = startX; i <= endX; i++)
 {
 for (int j = startY; j <= endY; j++)
 {
 filledCoordinates[i][j]++;
 if(filledCoordinates[i][j] == coordinatesNeeded)
 {
 return idx + 1;
 }
 }
 }
 }
 return -1;
}

Instead of checking every possible square, now you will only check the ones which could be the possible answer after the update.

Example with filledCoordinates following your example:

To help you visualize the squares, the first square is

11 0
11 0

The second is

0 11
0 11

So after (1, 2) filledCoordinates[0][0] = 1 filledCoordinates[0][1] = 1

after (2, 3) filledCoordinates[0][0] = 1 filledCoordinates[0][1] = 2

after (2, 1) filledCoordinates[0][0] = 2 filledCoordinates[0][1] = 2

after (1, 3) filledCoordinates[0][0] = 2 filledCoordinates[0][1] = 3

after (2, 2) filledCoordinates[0][0] = 3 filledCoordinates[0][1] = 4

We have reached coordinatesNeeded value and got our answer.

• CodeCrusader: can you please more details, on how the filledCoordinates works with an example, also in the above code matrix array is not being used in processing
• John: You probably do not need matrix array anymore, unless two points of input can be the same, then you would need an extra check to make sure not to count the same point twice.
• John: I added the example in edit. If the input array size is n, then for each update on our matrix we have to do up to k^2 updates on our filledCoordinates array so O(n * k^2)
• John: Probably should have not used the same variable, but i meant different n than the n of matrix, anyway, the corrected version then should be that if input array size is t and O(t * k^2)
• Fe2O3: Trivial feedback on variable names... This uses x related to 'rows' and y related to 'cols'. Nothing incorrect! Just that I find it 'jarring' when the names x & y don't correlate with conventions of the Cartesian coordinate system... Is it an abstract matrix with x&y, or is it a 'grid' of pixels? Easy to 'slip up' and make a mistake... Cheers :-)

Answer 3

Benchmarks with a Java implementation of my algorithm and with John's, times in seconds:

 n: 50 100 750 1500
your original 0.30 16.7 --- ---
John's 0.00 0.01 12.8 208.0
mine 0.00 0.01 0.13 0.42

The test case has n=m, k=n/2+1, and a center cell gets painted last (I think that's a worst case for all of us):

 public static void case5(int n) {
 int m = n, h = n / 2, k = h + 1;
 List<List<Integer>> paint = new ArrayList<>();
 for (int i=1; i<=n; i++)
 for (int j=1; j<=m; j++)
 if (i != h || j != h)
 paint.add(Arrays.asList(i, j));
 paint.add(Arrays.asList(h, h));
 long start = System.nanoTime();
 int answer = solve(n, m, k, paint);
 long end = System.nanoTime();
 System.out.println(answer + " " + (end - start) / 1e9);
 }

My solution:

 public static int solve(int n, int m, int k, List<List<Integer>> array) {
 int lo = 1, hi = n * m;
 while (lo < hi) {
 int mid = lo + (hi - lo) / 2;
 if (isValid(n, m, k, array, mid))
 hi = mid;
 else
 lo = mid + 1;
 }
 return lo;
 }
 
 public static boolean isValid(int n, int m, int k, List<List<Integer>> array, int answer) {
 int[][] matrix = new int[n+1][m+1];
 for (List<Integer> ij : array.subList(0, answer))
 matrix[ij.get(0)][ij.get(1)] = 1;
 int[][] P = new int[n+1][m+1];
 for (int i = 1; i <= n; i++)
 for (int j = 1; j <= m; j++)
 P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + matrix[i][j];
 for (int i = k; i <= n; i++)
 for (int j = k; j <= m; j++)
 if (P[i][j] - P[i-k][j] - P[i][j-k] + P[i-k][j-k] == k * k)
 return true;
 return false;
 }

• no comment: Could the downvoter please let me know how this is useless and how I can improve it?
• Peter Cordes: Not my downvote, but perhaps because it isn't a code review? But the OP didn't ask for one, so that's the fault of the question being off-topic. Or maybe because you have no text describing your approach and analyzing its big-O complexity-class? This would be a fairly good Stack Overflow answer, but Code Review expects more discussion. I only just noticed that this is your second answer on the question, so this could have been an edit to that answer unless you were hitting the 30k char limit. I could imagine a downvote for posting an answer that could (and arguably should) have been an edit.
• Fe2O3: Not my downvote, either... But the "timings" are meaningless... The OP wants evaluation after every 'pixel' coordinate arrives (as John's code does), terminating when a square has been filled-in anywhere on the 'canvas'. The timings for "finding a square after all pixels populated" should not be compared to John's version. This is not to say that your code is not interesting. It is.
• no comment: @Fe2O3 That is not true. What the OP wants is "I want to find the minimum position (that is index+1) in the array at which we will have the matrix having 1s in the form of a square of length k". And that is exactly what all three solutions do. The timings aren't meaningless, and the comparison is proper.
• Fe2O3: @nocomment "the minimum position (that is index+1) in the array" is the OP's language saying "the 'arrival' of each coordinate pair that paints one pixel in the matrix." The "index+1" is the index into the list of coordinate pairs being individually painted. You are free to disagree, naturally...

Answer 4

You could also try using 2D minimum range query. I think O(nmlog(n)log(m))

Or you could try to fill the array completely and keep track when each element was added, then you should need to go through all K*K squares and prune search if it contains bigger values than your best.

I think O is very close to nm in this because there is a lot of pruning. Maybe you could memorize something even more or improve it otherwise.

You could also try to calculate the minimum value which would guarantee at least one K*K square using math and improve it further.

Answer 5

Review fulfillment

The OP's code uses 'paired' variables named n & m, x & y, i & j, dx & dy... and k.
The reader may become flummoxed.

Consider the following using:
rows, row and r
cols, col and c
(and k, of course)

 public static int solve(int rows, int cols, int k, List...
 int[][] matrix = new int[rows][cols];
 ...
 // Get the coordinates to paint
 int r = array.get(idx).get(0) - 1; 
 int c = array.get(idx).get(1) - 1; 
 matrix[r][c] = 1;
 for (int row = 1; row <= rows - k; row++) {
 for (int col = 1; col <= cols - k; col++) {
 ...
 for (r = row; r < row + k; r++) {
 for (c = col; c < col + k; c++) {
 if (matrix[r][c] != 1) {

---

Apples and oranges

This problem and its solution has gotten under my skin for a number of reasons ranging from my own hasty and botched initial assessment and answer, to the OP's acceptance of the 'high performance' solution.

Two very fine blocks of code implementing algorithms have been given as solutions to the problem. One demonstrates insight providing a could-be-pricey solution that is quite easy to grasp. The other seems to be a juggernaut requiring careful consideration and much thought to fully appreciate.

Concerning to me is that the 'juggernaut' solution (as great as it is) disregards the word "sequentially" in the problem statement.

Consider a simpler analogy (where 'analogies' are not 'equalities'): The OP begins with a well-shuffled deck of cards. The objective is to sequentially go through the shuffled deck, halting when one turns-over the 3rd face card of any single suit of cards... The shuffled deck has its unique sequence, but the 'juggernaut' solution deals with entire slices of that entire deck in each iteration. It 'paints' ALL the pixels of that slice, assesses a result, then adjusts the slice size and 'starts over'. This approach would 'converge' on the answer, but does not implement the OP's stated requirement of sequentially determining when to halt.

Irrespective of what the OP's code does, careful reading of the problem statement leans toward on-the-fly determination of when the objective is attained, as opposed to waiting until the array is filled before getting to work.

One is left to question, "Apart from being a practice exercise, where might any solution be used in the real world?" If the entirety of the scrambled list array is available at once, the juggernaut analysis will win any time-trial competition in which k => k^2 is non-trivial. On the other hand, if "sequentially" has meaning in this problem, one might expect that array represents a 'drip feed' of matrix points to be 'set' and the appearance of a k-square to be determined as quickly (in real time) as possible. (No waiting around for the last of the points before starting to look for the target square. Picture a "Bingo Hall" with numbers being called out sequentially.)

In short, both presented solutions are insightful and appealing. However, to this reader of the problem, they solve different(!) real world scenarios. The OP presented code that demonstrates 'sequential', but, exercising their prerogative, accepted an (excellent) answer that deals best with 'batched' input; not-so-well if 'sequential' analysis of the input is required.

In conclusion: the 'juggernaut' approach would almost always require an entire herd of camels be sacrificed to fulfill this problem's search for its "straw that broke the camel's back" objective.
PETA would be furious.

---

Episode II: A New Hope

One can easily reason that the 'lightweight' solution degrades as the value of k increases.

Increasing k for a given [n][m] matrix may present opportunities to apply an alternate algorithm that improves as k increases.

Consider an example case where k = 8, n = m = 9. The sought after '8x8 square' will reside with one of its corners tucked into one corner of the 9x9 matrix. These four potential locations overlap forming a square region that is 7x7 (49) cells/pixels. SEQUENTIALLY setting any one of those 49 pixels to '1' simultaneously affects all four possible squares. MOST of the very few 'edge' pixels surrounding this common region are shared by two-of-four possible 'finished squares'. (In this specific example where m = n and k = m-1, each of the four corner pixels belongs to only one 'potential square'.)

In certain cases where k is greater than n/2 or m/2 (be careful!) there is the possibility that 2 or 4 'potential squares' overlap to some extent.

Using the above hypothetical specific case, the sequential 'arrival' of a matrix index from the array that falls within the overlapped region affects all four squares' 'tallies' toward the target k^2 threshold. Rather than traversing lots of tallying counters, incrementing each one, recognise that by being "common to all potential squares", its arrival can be recorded by lowering the threshold all four potential squares seek to attain. Its 'arrival' is acknowledged by recognising the adjusted threshold to complete a 'k-square' is now k^2 - 1. (NB: 'edge cells' of 1 or 2 squares - cells not in the overlap region - still must be incremented and tested.)

When any overlap region is small (can be as little as 1 pixel/cell), this would be quite a bit of fuss with little benefit. When the overlap is large (consider k = 98 while n = m = 99), the labour-saving benefit would be substantial.

It should be noted that, regardless of which algorithm is used, determining the 'location' of the first "completed k-square" may have to account for the particular "magic pixel" being common to more than one "completed k-square".

---

Conclusion

The wording of problem statements ('specifications') must be carefully considered. Does "sequentially" have any significance in the problem statement? (And, not forgotten, is the ambiguity of "square" being either "outline" or "filled".)

And, with experience in "Reversi/Othello/Iago", it's apparent that a player uses different strategies at different times during the play of one game. "One size fits all" may not be the optimal meta-strategy.

Note: Should the use-case tend toward larger 'k-squares' in smaller matrix canvasses, resulting in overlaps being typical, coding to reduce accesses to matrix cells held by the Java engine would also reduce Java's unknown "array bounds checking overhead" that may be being done for each access. Just a thought...

---

Afterthought

Consider that example of m = n = 99. The raw matrix would occupy 99^2 (9801) 'cells'. If k is typically going to be large (k = 98), implementing this 'overlap' algorithm would mean that 97x97 (9409) cells could be 'virtualised', not actually existing to serve this threshold adjusting algorithm.

This alternate algorithm, may even perform well against the 'juggernaut' algorithm in time trials for certain scenarios, even when dealing with 'batched input' of the entire array list being made available to both.

In the real world, the use-case would need to be taken into account to determine the coding complexity to implement. The OP did not ask about "space efficiency", but... well... there you are...

---

Like a dog with a bone...

Of the many potential sizes and shapes of matrix and the target value of k that could be 'given', an appreciable proportion of those WILL exhibit an "overlapping region" as described above. The previous paragraphs describe how the 'pixels' of the overlapped region need not be represented by elements in a memory matrix; the 'arrival' of the coordinates of one of those pixels merely reduces the 'threshold' to be attained by the 2 or 4 potential `k-squares.

The number of 'residual' cells may be quite small and each of those will belong to a some number of potential 'k-squares'.

The reader is invited to consider an algorithm to use when there is overlap that can be predetermined by the values of m & n and k, and in which ALL of the pixels are then 'virtual'. The coordinates of a 'pixel to be painted' can be translated to indices of an array of 'tabulators' that keep track of how many 'paint events' have occurred within the boundaries of the relatively few potential k-squares. (It helps to draw a number of 'canvases' in different shapes and sizes, marking overlaps for various values of k, then counting and considering how many potential k-square tabulators would be needed.)

Reiterating: the optimal solution often depends on the specific criteria of each instance. qsort is not the optimal strategy to invoke for very small arrays.