# Matched Brackets challenge

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 < buffer:
highest_depth = buffer
hpos = position -1 ##position of highest depth.
buffer -= 1
'''if buffer is now 0  due to the above line it must mean that all the
brackets opened have been closed.'''
if buffer == 0:
''' bar which calculates the max distance between two matched brackets
must be assigned now and reset to zero'''
if bar > stretch:
stretch = bar
stretch_pos = position - stretch + 1
bar = 0
print(highest_depth , hpos,stretch, stretch_pos)


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:

str = "1 2 3 4"
for index in range(0, len(str), 2):
num = str[index]
# use num here

• I see... I really didn't need to convert them to int. This should give me some speed. I will try it out when I get time after college. – sudo_dudo Jan 30 '17 at 4:49

I would extend @HeshamAttia's advice and suggest to use enumerate rather than maintaining your own position counter.

You should also give meaninful names to your data, so that it is easier to reason about the logic. Using the enum module, you can define:

class Symbol(enum.Enum):
OPEN_PARENTHESIS = '1'
CLOSE_PARENTHESIS = '2'


And use Symbol.OPEN_PARENTHESIS and Symbol.CLOSE_PARENTHESIS in the rest of the code so it is clearer what you are comparing and why.

Lastly, use functions, it help make the code more reusable, testable and readable. Something like:

import enum

class Symbol(enum.Enum):
OPEN_PARENTHESIS = '1'
CLOSE_PARENTHESIS = '2'

def parse_data(stream):
for character in stream:
try:
kind = Symbol(character)
except ValueError:
pass
else:
yield kind

def challenge(stream):
depth_pos = depth_max = depth = 0
span_pos = span = stretch = 0

for index, symbol in enumerate(stream):
stretch += 1
if symbol == Symbol.OPEN_PARENTHESIS:
depth += 1
elif symbol == Symbol.CLOSE_PARENTHESIS:
if depth_max < depth:
depth_max = depth
depth_pos = index - 1
depth -= 1

if not depth and span < stretch:
span = stretch
span_pos = index - stretch + 1
stretch = 0

return depth_max, depth_pos, span, span_pos

def main():