N-Queens Count all conflicts in O(n) time

Question

Count all the conflicts in a given n-Queen state.  It is easy to do in O(n²) time.  Give an O(n) time algorithm to count all conflicts.

Answer 1

We can count line by line to determine how many queens in a line.

For example, we take the horizontal direction as row by row from top to bottom.

In each row, we count how many queens in this row and get the number of conflicts= ((number of queens-1)+1)*(number of queens-1)/2.

There are almost n line in each direction and there is 4 direction.

So cost=4*n=O(n).

Comments

Take one row for example. If the length of the row is n, then you have to check each position in the row to confirm if there is a queen? Isn't it still be O(n)?
Then for each row, column and diagonal, doesn't it still cost O(n^2)?

---

Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, so if there is no queen and we do nothing. Only when we meet the queen position we take sum. So, for each direction we only take n sum function, even though we refresh sum to 0 at the start of each line.

---

for (int i = 0; i < size; i++)
            row[col[i]]++;
for (int i = 0; i <size; i++)
            if(col[i]<=i)
                diagonal[0][i-col[i]]++;
            else
                diagonal[0][size+col[i]-i]++;
for (int i = 0; i < size; i++)
        diagonal[1][col[i]+i]++;