jha_gaurav98's blog

Maximum Sub-square Sum in O(N2)
By jha_gaurav98, history, 6 years ago, In English

Given a square array of size N × N where each cell is filled with a number between  - 9 and 9. A sub square of size k is any set of k contiguous columns and k contiguous rows. For any sub square, the sum of elements in its cells is called a sub square sum. Given the N × N square, write a program to find the maximum sub square sum. (Note that a 1 × 1 square (k = 1) is not considered a sub square)

Constraints: 2 ≤ N ≤ 1000

By looking at the constraints I think we have to do it in O(N2). I could manage to reach to O(N3). Please Help

Thanks in advance

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (7)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by jha_gaurav98 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +9 Vote: I do not like it

Are you sure that N^3 isn't enough? The constant is quite low maybe if you use memory efficiently for cache it's enough?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Actually I have to appear for the coding round for a company coming to my campus. They gave a pdf file containing a sample test and I just copied this from that. Since the constraint is N ≤ 1000 , I thought it had to be done in O(N2). But now I think may be they will do the code review or something like that to check the correctness of code.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By the way , can you think something like applying kadane's algorithm in diagonal elements because one of my friends said that it can be done in O(N2) and he tried to explain something like apply kadane algorithm in diagonal elements but I couldn't get what he wanted to say.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it +8 Vote: I do not like it

      Kadane's algo applies to 1d problem only. If you traverse the grid diagonally, you have to vary both the height and the width. That becomes a 2d problem.

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

I personally don't know any solution for this problem that is faster than O(N3). However, I think that you may be able to squeeze this solution under the time limit with the help of loop unrolling. Your code will look a little ugly. But it does wonders sometimes.

Generate 999 (because we don't consider 1x1 squares) switch cases in descending order. For each case, you fix a rectangle size and search the grid. Remember to remove break statements from the switch so that when N = X where 2 ≤ X ≤ 1000, then all squares of size X * X, (X - 1) * (X - 1), (X - 2) * (X - 2)... will be searched. You can easily get the sum of each candidate square in O(1) using inclusion-exclusion. So the total time-complexity is still O(N3). I am not sure how fast this approach would be. But this is the best that I can think of.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey actually this question is part of a company's hiring process and I don't think that they will be expecting something like this. By the way your idea was nice. Thanks

    → Reply