Python O(n) solution beat 99.86%


  • 0
    J
    class Solution(object):
        def maxDistance(self, arrays):
        	# Keywords: Array
        	n = len(arrays)
    
        	# Initialize the values and positions for the first and second largest numbers
        	if arrays[1][-1] > arrays[0][-1]:
        		large1Val, large1Pos, large2Val, large2Pos = arrays[1][-1], 1, arrays[0][-1], 0
        	else:
        		large1Val, large1Pos, large2Val, large2Pos = arrays[0][-1], 0, arrays[1][-1], 1
    
        	# Initialize the values and positions for the first and second smallest numbers
        	if arrays[1][0] < arrays[0][0]:
        		small1Val, small1Pos, small2Val, small2Pos = arrays[1][0], 1, arrays[0][0], 0
        	else:
        		small1Val, small1Pos, small2Val, small2Pos = arrays[0][0], 0, arrays[1][0], 1
    
        	# Iterate all the arrays and update the variables above
        	for i in range(2,n):
        		if arrays[i][-1] > large2Val:
        			large2Val, large2Pos = arrays[i][-1], i
        			if large2Val > large1Val:
        				large1Val, large1Pos, large2Val, large2Pos = large2Val, large2Pos, large1Val, large1Pos
    
        		if arrays[i][0] < small2Val:
        			small2Val, small2Pos = arrays[i][0], i
        			if small2Val < small1Val:
        				small1Val, small1Pos, small2Val, small2Pos = small2Val, small2Pos, small1Val, small2Pos
    
        	if large1Pos != small1Pos:
        		return large1Val - small1Val
        	else:
        		return max(large2Val - small1Val, large1Val - small2Val)
    

Log in to reply
 

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