HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMinor

Matched Brackets challenge

Submitted by: @import:stackexchange-codereview··
0
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:

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

Code Snippets

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

Context

StackExchange Code Review Q#153945, answer score: 4

Revisions (0)

No revisions yet.