title: Turning negative entries positive in a matrix by checking adjacent entries- only certain conversions allowed each pass, what's the time complexity?
body: <p>I am given an <code>(nxm)</code> matrix of <code>positive and negative integers</code>.</p>
  <p>The goal is to try and convert all negative numbers into positive ones, and if this is possible, return the <code>number of passes</code> of the matrix required to do this, otherwise <code>return -1</code>.</p>
  <p>Here are the rules:</p>
  <ul>
  <li>You can only convert a negative number into a positive one, if the negative number has an adjacent (directly above, below, left or right) entry that is positive.</li>
  <li>If you convert a number from negative to positive in a certain pass, you cannot then use this (recently) turned positive number to turn other negative numbers positive- at least for this pass.</li>
  </ul>
  <p>I have written an accepted solution to the problem, but I can't seem to work out the <code>Time Complexity</code> of the solution.</p>
  <p>My solution:</p>
  <ol>
  <li><p>Create a <code>Boolean matrix</code> to mark the negative entries that have been turned positive in the current pass (we will reset this matrix after each pass)</p>
  </li>
  <li><p>Iterate over all entries of the matrix</p>
  </li>
  <li><p>For every negative number we stumble across check all 4 of its adjacent entries and see if there are any positive entries.
  If so, convert it to positive and mark it in the boolean matrix.</p>
  </li>
  <li><p>Increment <code>number of passes</code> each time we iterate over the whole matrix.</p>
  </li>
  <li><p>We are done when we iterate over the entire matrix and have not made a single change to it (i.e. conversion from negative to positive).</p>
  </li>
  <li><p>If there are any negative entries left, <code>return -1</code>, otherwise return the <code>number of passes</code>.</p>
  </li>
  </ol>
  <p>I can't seem to think of a worst case- any suggestions on the time complexity of this solution?
  My initial thought are that it is O(n), where n is the size of the matrix.</p>
  <p>For reference, here is my solution:</p>
  <pre><code>def minimumPassesOfMatrix(matrix):
      numberOfPasses = 0
      ChangesMade = True
  
      while ChangesMade:
          negToPosMarket = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
          ChangesMade = False
          for row in range(len(matrix)):
              for col in range(len(matrix[0])):
                  if matrix[row][col] &lt; 0:
                      positiveAdjacent = checkAdjacentEntriesForPositive(matrix, row, col, negToPosMarket)
                      if positiveAdjacent:
                          matrix[row][col] *= -1
                          negToPosMarket[row][col] = True
                          ChangesMade = True
          if not ChangesMade:
              break
          numberOfPasses += 1
  
      if all(matrix[row][col] &gt;= 0 for row in range(len(matrix)) for col in range(len(matrix[0]))):  #notebook double for loop list comp!
          return numberOfPasses
  
      print(matrix)
  
      return -1
  
  
  def checkAdjacentEntriesForPositive(matrix, row, col, negToPosMarket):
      matrixHeight = len(matrix) - 1
      matrixWidth = len(matrix[0]) - 1
  
      if not OutOfBounds(row + 1, col, matrixHeight, matrixWidth) and not negToPosMarket[row + 1][col]:
          if matrix[row + 1][col] &gt; 0:
              return True
      if not OutOfBounds(row - 1, col, matrixHeight, matrixWidth) and not negToPosMarket[row - 1][col]:
          if matrix[row - 1][col] &gt; 0:
              return True
      if not OutOfBounds(row, col + 1, matrixHeight, matrixWidth) and not negToPosMarket[row][col + 1]:
          if matrix[row][col + 1] &gt; 0:
              return True
      if not OutOfBounds(row, col - 1, matrixHeight, matrixWidth) and not negToPosMarket[row][col - 1]:
          if matrix[row][col - 1] &gt; 0:
              return True
  
      return False
  
  
  def OutOfBounds(row, col, matrixHeight, matrixWidth):
      return row &lt; 0 or col &lt; 0 or row &gt; matrixHeight or col &gt; matrixWidth
  </code></pre>