patternpythonMinor
Matched Brackets challenge
Viewed 0 times
matchedbracketschallenge
Problem
I am attempting the matched brackets problem. I have written a Python program which seems to do the job but is very slow and thus exceeds the time limit. Please help me making this code more efficient. I have explained my code in the comments.
length = int(input())
inp = input().split(' ')
inp = [ int(x) for x in inp ]
position = 0 ##where our cursor is.
highest_depth =0
buffer = 0
stretch = 0 ##max distance b/w two matched brackets.
bar = 0 ## jst a buffer for calculating max distance between two brackets.
stretch_pos = 0
for l in inp:
position += 1
bar += 1
'''if the cursor is currently at open bracket(1) add 1 to buffer'''
if l == 1:
buffer += 1
else:
'''if the cursor is at a closed bracket(2) we need to stop calculating
higest depth and assign it to highest_depth only if the current value
is smaller'''
if highest_depth stretch:
stretch = bar
stretch_pos = position - stretch + 1
bar = 0
print(highest_depth , hpos,stretch, stretch_pos)Solution
I think your algorithm is fast enough to get accepted. Contest times are sometimes not well calibrated for python speed.
One part that could be optimized is splitting the string and converting it to integers, which is now creating a new string for every number, possibly up to \$10^5\$ strings. Since the string is always gonna be 1-digit numbers separated by spaces, you could instead iterate on the string without parsing it or converting it to integers.
Something like:
One part that could be optimized is splitting the string and converting it to integers, which is now creating a new string for every number, possibly up to \$10^5\$ strings. Since the string is always gonna be 1-digit numbers separated by spaces, you could instead iterate on the string without parsing it or converting it to integers.
Something like:
str = "1 2 3 4"
for index in range(0, len(str), 2):
num = str[index]
# use num hereCode Snippets
str = "1 2 3 4"
for index in range(0, len(str), 2):
num = str[index]
# use num hereContext
StackExchange Code Review Q#153945, answer score: 4
Revisions (0)
No revisions yet.