title: How can I make the performance O(N) instead of O(N^2)?
body: <p>I'm trying to understand how to make the time complexity better for this problem:</p>
  
  <blockquote>
    <p>A non-empty zero-indexed array A consisting of N integers is given.
    The consecutive elements of array A represent consecutive cars on a
    road.</p>
    
    <p>Array A contains only 0s and/or 1s: 0 represents a car traveling east, 1 represents a car traveling west.</p>
    
    <p>The goal is to count passing cars. We say that a pair of cars (P, Q),
    where 0 ≤ P &lt; Q &lt; N, is passing when P is traveling to the east and Q
    is traveling to the west.</p>
    
    <p>For example, consider array A such that:</p>
  
  <pre><code>A[0] = 0   
  A[1] = 1   
  A[2] = 0   
  A[3] = 1   
  A[4] = 1 
  </code></pre>
    
    <p>We have five pairs of passing cars: (0, 1), (0, 3), (0, 4), (2, 3), (2, 4).</p>
    
    <p>Write a function:</p>
  
  <pre><code>int solution(NSMutableArray *A);
  </code></pre>
    
    <p>that, given a non-empty zero-indexed array A of N integers, returns
    the number of pairs of passing cars.</p>
    
    <p>The function should return −1 if the number of pairs of passing cars
    exceeds 1,000,000,000.</p>
    
    <p>Assume that:</p>
    
    <p>N is an integer within the range [1..100,000]; each element of array A
    is an integer that can have one of the following values: 0, 1.</p>
    
    <p>Complexity:</p>
    
    <p>expected worst-case time complexity is O(N); expected worst-case space
    complexity is O(1), beyond input storage (not counting the storage
    required for input arguments). Elements of input arrays can be
    modified.</p>
  </blockquote>
  
  <p>Solution:</p>
  
  <pre><code>   int solution(NSMutableArray *A) {
  // write your code in Objective-C 2.0
  
  int counter = 0;
  
  for (int i = 0; i &lt; A.count; i++) {
      if ([A[i] intValue] == 0) {
          for (int j = i; j &lt; A.count; j++) {
              if ([A[j] intValue] == 1) {
                  counter++;
              }
          }
      }
  }
  
  
  return counter;
  }
  </code></pre>
  
  <p>Right now the solution is running at O(N^2) due to the nested for loops. I cant seem to wrap my head around how to solve it in O(N) time. This isn't homework; I'm just refreshing algorithms for interviews.</p>