# How many cross lines in unsorted array

• The title of the question is not complete. Here is explanation:
Given an unsorted array. for example [2, 3, 1, 4, 5].
Sort the array, we have new array [1, 2, 3, 4, 5],
if we draw the line between the 2 arrays for the same number, for example:

``````[3, 2, 1,4,5]
\ | /
\|/
/|\
[1, 2, 3,4,5]
``````

then we have 3 line-cross:

1. line (1 to 1) cross line (2 to 2)
2. line (1 to 1) cross line (3 to 3)
3. line (2 to 2) cross line (3 to 3)

Implement the algorithm to calculate the how many line crosses for an unsorted array.

• my solution is

• Find all elements that will not moved after sort.
• Check every elements got in step 1, if every elements before it less than it. it's a element who doesn't cross, count 1
• Use list's size minus no cross number
``````def number_of_cross(list):
sl = list[:]
sl.sort()
noCross = 0

for i in range(len(list)):
if sl[i] == list[i]:
allLess = True
for j in range(i):
if list[j] > list[i]:
allLess = False
break

if allLess:
noCross = noCross + 1

return len(list) - noCross

if __name__ == "__main__":
print(number_of_cross([3, 2, 1, 4, 5]))``````

• @billyean ,
if the array is [4, 3, 2, 1], the number of line crosses is 3+2+1=6. So the solution is incorrect.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.