279. Perfect Squares

Hello, reader 👋🏽 ! Welcome to day 52 of the series on Problem Solving. Through this series, I aim to pick up at least one question everyday and share my approach for solving it.

Today, I will be picking up LeetCode's daily challenge problem: 279. Perfect Squares.

🤔 Problem Statement

Given an integer n, return the least number of perfect square numbers that sum to n.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.
E.g.:
- n = 12 => 3
  - 12 = 4 + 4 + 4
- n = 13 => 2
  - 13 = 4 + 9

💬 Thought Process - Breadth First Search

This question can be sort of visualised as a graph problem where a number's immediate neighbour's would be the number subtracted by the square of numbers starting from 1.
For e.g., the neighbours for 12 would be: 12-1 = 11, 12-4 = 8, 12-9 = 3.
- We only need to subtract squares of numbers until the square root of the current number. In this case sqrt(12) = 3.6.
Why square root of the current number? If you see the above example, if we try to subtract 16 (square of 4) from 12, the resultant number becomes less than 0.
- Mathematically, we can see that the sum of squares would be within the square root of any number.
This sounds like BFS where we need to keep finding the first level of neighbours, the second level, third and so on.
We'll use a queue to keep track of neighbours of a number and begin the traversal by adding the input n to the queue.
There should also be a track of nums which represents the number of perfect squares.
We'll then process all the neighbours in the same level together and find the immediate neighbours of all these numbers from 1 to sqrt(number).
If we find any perfect square which when subtracted from the current number results in 0, we simply return nums.
We should also ensure that we add every number only once. For e.g.,
- Neighbours of 12 are: 11, 8, 3 => add to queue
  - Neighbours of 11: 10, 7, 2 => add to queue
  - Neighbours of 8: 7, 4 => add 4 to queue as 7 is already present
- Notice that 7 was already added to queue as a result of 11's neighbour. Hence we should not add it again while finding neighbours of 8.
It is also worth noting that every number can be represented as a sum of perfect squares. Hence we are guaranteed to find an answer.
A dry run for n = 12
1. Queue: 12
  - poll 12
    - Neighbours: 11, 8, 3
    - Add to queue: 11, 8, 3
2. Queue: 11, 8, 3
  - poll 11
    - Neighbours: 10, 7, 2
    - Add to queue: 10, 7, 2
  - poll 8
    - Neighbours: 7, 4
    - Add to queue: 4
  - poll 3
    - Neighbours: 2
3. Queue: 10, 7, 2, 4
  - poll 10
    - Neighbours: 9, 6, 1
    - Add to queue: 9, 6, 1
  - poll 7
    - Neighbours: 6, 3
  - poll 2
    - Neighbours: 1
  - poll 4
    - Neighbours: 3, 0
    - We found 0, hence return level = 3

👩🏽‍💻 Solution - Breadth First Search

Below is the code for the BFS approach.

class Solution {
  public int numSquares(int n) {
      if(n <= 0) return -1;

      Queue<Integer> queue = new LinkedList();
      Set<Integer> set = new HashSet();
      queue.add(n);
      set.add(n);

      int numbers = 0;

      while(!queue.isEmpty()) {
          numbers++;
          int size = queue.size();

          while(size-- > 0) {
              int num = queue.poll();

              for(int i = 1; i <= Math.sqrt(num); i++) {
                  int nextNum = num - (i*i);
                  if(nextNum == 0) return numbers;
                  if(!set.contains(nextNum)) {
                      set.add(nextNum);
                      queue.add(nextNum);
                  }
              }
          }
      }

      return numbers;
  }
}

Time Complexity: O(n * sqrt(n))
Space Complexity: O(n)

💬 Thought Process - Memoization

We can also use recursion to solve this problem. But since we will have overlapping sub-problems (like we saw above when multiple numbers can have same neighbours), this would lead to TLE and is not efficient.
Hence, we can memoize values that are calculated at any n so that when we get an already solved sub-problem, we can return the cached answer.
We'll follow the same approach where for every n, we shall try to find it's neighbours by subtracting squares of numbers from 1 to square root of the current number.
We find the minimum of the answer we have so far (initially Integer.MAX_VALUE) and the answer for the next neighbour.
If at any point n becomes less than 0, return Integer.MAX_VALUE and if n becomes 0, return 0.
Once all the squares have been subtracted from the current n, we will have the minimum number of steps (or levels) that would sum up to the input. We finally return the answer + 1.
When n = 12, a few calls that would happen are:
- n = 11, answer = 12 => represents subtracting 1 until n = 0.
- n = 8, answer = 8 => represents 9 where subtract 4 from 12, then subtract 1 from 8, eight times to result in 0.
After recursively exhausting the neighbours of every n, we'll get the answer to be 3 (which is the minimum).

👩🏽‍💻 Solution - Memoization

Below is the code for the DP memoization approach.

class Solution {
  public int numSquares(int n) {
      if(n <= 0) return 0;

      int[] memoized = new int[n+1];
      Arrays.fill(memoized, -1);
      return numberOfPerferSquares(n, memoized);
  }

  private int numberOfPerferSquares(int n, int[] memoized) {
      if(n < 0) return Integer.MAX_VALUE;
      if(n == 0) return 0;

      if(memoized[n] != -1) return memoized[n];

      int answer = Integer.MAX_VALUE;
      for(int i = 1; i <= Math.sqrt(n); i++) {
          int nextNum = n - (i*i);
          int nextAnswer = numberOfPerferSquares(nextNum, memoized);
          answer = Math.min(answer, nextAnswer);

      }

      return memoized[n] = answer + 1;
  }
}

Time Complexity: O(n*sqrt(n))
Space Complexity: O(n)

💬 Thought Process - Tabulation

We can also convert the above memoized solution to tabulation.
First we'll keep the same 1D array of size n that would cache the previously solved problems.
Then we'll handle the base cases similarly as well. So dp[0] = 0.
We'll start the iteration from i = 1 to i = n. This i represents the goal which is to be obtained by the sum of perfect squares.
For every n, we will iterate from j = 1 to j = sqrt(i). Here for every dp[i], we try to find the minimum of number = i - (j * j), dp[number], for all number >= 0.
Once the inner j loop ends, we set the dp[i] to 1 + min(number).
After both the loop ends, we will have the number of sum of squares in dp[n].

👩🏽‍💻 Solution - Tabulation

Below is the code for the tabulation approach.

class Solution {
  public int numSquares(int n) {
      if(n <= 0) return 0;

      int[] dp = new int[n+1];
      dp[0] = 0;

      for(int i = 1; i<=n; i++) {
          int answer = Integer.MAX_VALUE;

          for(int j = 1; j<=Math.sqrt(i); j++) {
              int nextNum = i - (j * j);
              if(nextNum < 0) {
                  continue;
              }

              int nextAnswer = dp[nextNum];
              answer = Math.min(answer, nextAnswer);
          }

          dp[i] = answer + 1;
      }
      return dp[n];
  }
}

Time Complexity: O(n*sqrt(n))
Space Complexity: O(n)

You can find the link to the GitHub repo for this question here: 279. Perfect Squares.

Conclusion

That's a wrap for today's problem. If you liked my explanation then please do drop a like/ comment. Also, please correct me if I've made any mistakes or if you want me to improve something!

Thank you for reading!

Bharati Subramanian