algoadvance

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n^2 in spiral order.

Clarifying Questions

1. Q: What should be the starting point for the spiral? A: The spiral should start from the top-left corner of the matrix.

2. Q: Should the numbers be increasing sequentially? A: Yes, the numbers should start from 1 and increase sequentially up to n^2.

3. Q: Is there any constraint on the size of n? A: The problem specifies n as a positive integer, so n will be at least 1.

Strategy

1. Create an n x n matrix initialized with zeros.
2. Define boundaries: We need four boundaries top, bottom, left, and right to control the spiral direction as we fill the matrix.
3. Set initial values: Start the current number at 1 and iterate until reaching n*n.
4. Fill the matrix in a spiral order by adjusting boundaries:
   • Move from left to right on the top row.
   • Move from top to bottom along the right column.
   • Move from right to left on the bottom row.
   • Move from bottom to top along the left column.
5. Adjust the boundaries each time a complete row or column is filled.

Code

def generateMatrix(n):
    matrix = [[0] * n for _ in range(n)]
    top, bottom, left, right = 0, n - 1, 0, n - 1
    num = 1
    
    while top <= bottom and left <= right:
        # Fill the top row
        for i in range(left, right + 1):
            matrix[top][i] = num
            num += 1
        top += 1
        
        # Fill the right column
        for i in range(top, bottom + 1):
            matrix[i][right] = num
            num += 1
        right -= 1
        
        # Fill the bottom row
        for i in range(right, left - 1, -1):
            matrix[bottom][i] = num
            num += 1
        bottom -= 1
        
        # Fill the left column
        for i in range(bottom, top - 1, -1):
            matrix[i][left] = num
            num += 1
        left += 1
    
    return matrix

Time Complexity

• Time Complexity: The algorithm fills each cell in the n x n matrix exactly once, so the time complexity is (O(n^2)).
• Space Complexity: The space complexity is (O(n^2)) because the algorithm creates an n x n matrix to store the results.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?