You will be given a string s. It is guaranteed that the string has equal and at least one [s and ]s. It is also guaranteed that the brackets are balanced. The string can also have other characters.

The objective is to output/return a list of tuples or a list of lists containing indices of each [ and ] pair.

note: The string is zero-indexed.

Example: !^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][] should return

[(8, 41), (20, 33), (21, 27), (36, 39), (42, 48), (49, 50)] or something equivalent to this. Tuples are not necessary. Lists can also be used.

Test cases:

input:[[asdf][][td([)ty54g% ]hg[[f]u][f[[jhg][gfd]sdf]sdfs]ghd]fr43f]
output:[(0, 62),(1, 6), (7, 8), (9, 56), (13, 22), (25, 30), (26, 28), (31, 52), (33, 47), (34, 38), (39, 43)]
output:[(0, 9), (1, 2), (3, 4), (5, 6), (7, 8), (10,26),(11, 12), (13, 14), (15, 16), (17, 25), (18, 24), (19, 23), (20, 22)]
output:[(0, 1), (2, 3), (4, 7), (5, 6)]
output:[(0, 21), (1, 17), (2, 14), (3, 11), (4, 8), (22, 23), (24, 25)]
output:[(0, 5), (1, 3)]

This is , so the shortest code in bytes for each programming language wins.

  • 1
    \$\begingroup\$ Does the output order matter? \$\endgroup\$
    – wastl
    Commented Jun 7, 2018 at 17:04
  • 1
    \$\begingroup\$ no, it does not. \$\endgroup\$ Commented Jun 7, 2018 at 17:05
  • 22
    \$\begingroup\$ "note: The string is zero-indexed." - It's very common to allow implementations to choose a consistent indexing in these kind of challenges (but it is, of course, up to you) \$\endgroup\$ Commented Jun 7, 2018 at 17:05
  • 1
    \$\begingroup\$ Can we take input as an array of characters? \$\endgroup\$
    – Shaggy
    Commented Jun 7, 2018 at 17:31
  • 7
    \$\begingroup\$ Costs one byte... \$\endgroup\$
    – dylnan
    Commented Jun 7, 2018 at 18:28

25 Answers 25


Brain-Flak Classic, 108 bytes


Try it online!

Stores each opening [ in the right stack, and outputs whenever we hit a ].


Python 2, 74 bytes

for c in input():
 if']'==c:print s.pop(),i

Try it online!


JavaScript, 69 62 bytes

A quick bit of golf on the train home. Can probably be improved on.

Takes input as an array of characters and outputs an object with the keys being the indices of the [s and their values being the indices of their corresponding ]s.


Try it online

  • \$\begingroup\$ It blows my mind that you can golf on mobile. :P \$\endgroup\$
    – Oliver
    Commented Jun 7, 2018 at 18:09
  • 2
    \$\begingroup\$ @Oliver, it blows my mind that I can (just about) type on touchscreens at all - bring back keyboards! \$\endgroup\$
    – Shaggy
    Commented Jun 7, 2018 at 18:36

Haskell, 92 79 bytes

g(u:a)n(']':x)=(u,n):g a(n+1)x
g a n(s:x)=g([n|s=='[']++a)(n+1)x

Try it online!


We create a function g which takes 3 arguments.

  • a, which is the locations of all unmatched [s.

  • n, which is the number of characters processed

  • x which is the characters unprocessed.

If our first character is ] we remove u from the front our a and return (u,n) plus whatever else remains.

g(u:a)n(']':x)=(u,n):g a(n+1)x

If our first character is not ], that is either [ or something else, we increment n and add [n|s=='['] to the front of a. [n|s=='['] will be [n] if s=='[' and [] otherwise.

g a n(s:x)=g([n|s=='[']++a)(n+1)x

If we are out of characters we return the empty list.

  • 1
    \$\begingroup\$ wow, thats some nice piece of recursive functions. I'm a beginner on Haskell, this impressed me:) \$\endgroup\$ Commented Jun 7, 2018 at 17:01
  • \$\begingroup\$ @gnu-nobody Thanks! This answer is probably not optimal, so I would encourage you to try and beat it, or wait until the serious Haskell golfers arrive. \$\endgroup\$
    – Wheat Wizard
    Commented Jun 7, 2018 at 17:08
  • \$\begingroup\$ I'd better wait until the serious Haskell golfers arrive \$\endgroup\$ Commented Jun 7, 2018 at 17:09

Java 10, 95 bytes

A void lambda taking the input string as an int[] of Unicode code points.

s->{int r=0,w=0;for(var c:s){if(c==91)s[w++]=r;if(c==93)System.out.println(s[--w]+","+r);r++;}}

Try It Online


s -> {
    int r = 0, w = 0;
    for (var c : s) {
        if (c == 91)
            s[w++] = r;
        if (c == 93)
            System.out.println(s[--w] + "," + r);


  • thanks to Jonathan Frech for the idea of using the input string as a stack (here)
  • \$\begingroup\$ You must define r and w as part of the code, not as parameters: s->{int r=0,w=0;...}. \$\endgroup\$ Commented Jun 7, 2018 at 21:10
  • \$\begingroup\$ @OlivierGrégoire Kind of ambiguous, but this looks like it was intended to cover multiple empty inputs. \$\endgroup\$
    – Jakob
    Commented Jun 7, 2018 at 21:19
  • 1
    \$\begingroup\$ The answer you quote explicitly answers the question "Are we allowed to take an empty parameter instead we won't use anywhere?". You're using these inputs. I see no ambiguity at all here. \$\endgroup\$ Commented Jun 7, 2018 at 21:20
  • \$\begingroup\$ The edit part of the question makes it absolutely unambiguous about the "no-use" the variable. \$\endgroup\$ Commented Jun 7, 2018 at 21:30
  • \$\begingroup\$ Right, but then why does the top answer (1) not state that inputs are unused, (2) specify what the values of extra inputs are, and (3) mention the possibility of abusing extra inputs? Regardless, I'll move the variables. \$\endgroup\$
    – Jakob
    Commented Jun 7, 2018 at 21:43

vim, 89 bytes

:s/\(.\)/\1<C-V><C-M>/g|g/^\[/ :norm %mm%:pu! =line('.').','.line(\"'m\")<C-V><C-M><C-X>$<C-X>J


:s/\(.\)/\1<C-V><C-M>/g            " one character per line
|g/^\[/                            " for each opening square bracket:
  :norm %mm%                       "   mark the line with the matching bracket
  :pu! =line('.').','.line(\"'m\") "   write the line numbers to preceeding line
  <C-V><C-M><C-X>$<C-X>J           "   convert to 0-based counting and join lines
:v/\[/d                            " remove all non-opening bracket lines
|%s/\[//g                          " remove brackets

<C-V> is 0x16. <C-M> is 0x0d. <C-X> is 0x18.

Try it online!


QBasic (QB64), 137 127 112 bytes

for i=0to len(a$)

We need four two bytes because the challenge requires 0-indexing. My first QBasic post, feedback is appreciated.

  • 10 bytes thanks to steenbergh
  • 3 bytes thanks to Erik the Outgolfer
  • 12 bytes by saving in unix file format (\r\n -> \n)

Looks like this when executed:

How it looks

  • \$\begingroup\$ Nice one. Couple of pointers: use ? instead of print (the compiler auto-expands this to print), you don't need the spaces between the quoted strings and THEN in the IFs, and you can drop the i after NEXT. \$\endgroup\$
    – steenbergh
    Commented Jun 7, 2018 at 18:25
  • \$\begingroup\$ @steenbergh Huh, seems I forgot to remove whitespace ... but I removed the one between 0 and to? I'm confused ... \$\endgroup\$
    – wastl
    Commented Jun 7, 2018 at 19:06
  • 1
    \$\begingroup\$ Not sure about QB64, but I think if c$="[" can become if"["=c$, elseif c$="]" can become elseif"]"=c$, end if can become endif, and, with a slight change in the output, ?b(n),i can become ?b(n)i (QBasic 1.1 is what I use, your case might be different). \$\endgroup\$ Commented Jun 8, 2018 at 11:42
  • \$\begingroup\$ @EriktheOutgolfer all but ?b(n)i worked \$\endgroup\$
    – wastl
    Commented Jun 8, 2018 at 12:11

Pyth, 26 bytes


Try it here


VQ                     =hZ   For each character in the input (indexed by Z)...
  IqN\[=+YZ)                 ... if the character is [, add the index to Y...
            IqN\],.)YZ)      ... if the character is ], output the previous index
                             and current index.
  • \$\begingroup\$ Nice! My naïve approach was 36 bytes, C,x"[" MQ #.e*qb\[t+lhfSI/LT"[]"._>Q. Edit: I succeeded golfing mine quite a bit too, I'm now below 30. \$\endgroup\$
    – Mr. Xcoder
    Commented Jun 7, 2018 at 17:17

Jelly, 20 18 bytes

Saved 1 byte thanks to @user202729 informing me that µ€ is )


Try it online!

After wrestling with this for several hours just to get it working... I'm honestly surprised that it's gotten this short :-)


ẹⱮØ[µ³ḣċþØ[_/Ụị)Z’   Main link. Argument: s (string)  '[a[b]c[]][d]'
  Ø[                 Shortcut for the string "[]".
 Ɱ                   For each char in the "[]":
ẹ                      Find the indices of each occurrence in the input.
                     For our example, this gives the array [[1, 3, 7, 10], [5, 8, 9, 12]].

    µ                Begin a new monadic chain, with said array as its argument.
               )     For each of the two sub-arrays q within the array:
                         [[1, 3, 7, 10], [5, 8, 9, 12]]
     ³ḣ                For each item n in q, take the first n chars of the input.
                         [['[',     '[a[',      '[a[b]c[',   '[a[b]c[]]['],
                          ['[a[b]', '[a[b]c[]', '[a[b]c[]]', '[a[b]c[]][d]']]
        þØ[            For each string s in this, and each char c in "[]":
       ċ                 Count the occurrences of c in s.
                         [[[1, 0],  [2, 0],     [3, 1],      [4, 3]],
                          [[2, 1],  [3, 2],     [3, 3],      [4, 4]]]
           _/          Reduce each pair by subtraction. This is the number of open brackets
                         at each position.
                         [[1, 2, 2, 1], [1, 1, 0, 0]]
             U         Sort the indices by their values, using position as a tiebreaker.
                         [[1, 4, 2, 3], [3, 4, 1, 2]]
              ị        Index these values back into q.
                         [[1, 10, 3, 7], [9, 12, 5, 8]]

               )     Start a new monadic chain with the result as its argument.
                Z    Zip; transpose rows and columns.
                         [[1, 9], [10, 12], [3, 5], [7, 8]]
                 ’   Decrement; switch to 0-indexing.
                         [[0, 8], [9, 11], [2, 4], [6, 7]]

R, 141 133 115 112 108 bytes

function(y,x=utf8ToInt(y)){for(i in seq(x)){if(x[i]==91)F=c(i,F);if(x[i]==93){T=c(T,F[1],i);F=F[-1]}};T[-1]}

Try it online!

Nothing special. 1-indexed, because I said so. R doesn't really have stacks, so I originally used c, head, and tail to get the same literal effect. Ungolfed original version (updates using utf8ToInt to remove some bytes, using the start of the vector as the top of the stack, and abusing T and F builtins to avoid initializing the stacks.):

f <- function(y, x=el(strsplit(y,""))) {
  p <- l <- NULL
  for(i in seq_along(x)) {
    if(x[[i]]=='[') {
      p <- c(p, i)
    if(x[[i]]==']') {
      l <- c(l, tail(p, 1), i)
      p <- head(p, -1)
  l # Because I said so. Change to l-1 if you want to check the test cases.
  • \$\begingroup\$ Save some bytes by abusing built-ins T`` and F` \$\endgroup\$
    – JayCe
    Commented Jun 8, 2018 at 19:21
  • \$\begingroup\$ and 1:nchar(y) is shorter than seq_along(x). Very nice solution btw :) \$\endgroup\$
    – JayCe
    Commented Jun 8, 2018 at 19:23
  • \$\begingroup\$ I wonder if gregexpr is the way to go. \$\endgroup\$
    – ngm
    Commented Jun 8, 2018 at 19:53
  • \$\begingroup\$ I had originally tried to leverage this approach but I am not sure if this is the right way here. \$\endgroup\$
    – JayCe
    Commented Jun 9, 2018 at 13:32
  • \$\begingroup\$ JayCe solution is flawed (check the result, it returns 22 28 22 instead of 22 28 21) probably the (ab)use of T/F is not really safe :D. This is shorter and seems to work --> Try it online! \$\endgroup\$
    – digEmAll
    Commented Jun 9, 2018 at 13:53

Forth (gforth), 75 bytes

: f 0 do dup i + c@ dup 91 = if i s>f then 93 = if f>s . i . cr then loop ;

Try it online!

Abuses the floating-point stack, but allows using a do loop since the code doesn't (manually) touch the return stack.


  1. Loop through characters in string
  2. Check each character
    1. If equal to [, put on floating point stack
    2. if equal to ] pop from floating point stack and output with current position

Code Explanation

0 do                 \ start a loop from 0 to string-length
  dup                \ duplicate the starting address to avoid losing it
  i + c@             \ get the address of the current position and retrieve the character
  dup                \ duplicate the character, to allow checking twice
  91 = if            \ if char = [
    i s>f            \ store the current address on the floating point stack
  then               \ end the if-statement
  93 = if            \ if char = ]
    f>s .            \ pop the starting position from the float-stack and print
    i .              \ print the current position
    cr               \ output a newline
  then               \ end the if-statement
loop                 \ end the loop

Retina, 36 bytes


Try it online! Explanation:


Generate a list from the match results.


Use the following substitution to generate the list instead of the matches.


Allow matches to overlap.


This is an application of .NET's balancing groups. The [ is matched literally, then as many characters as possible are consumed. As each subsequent [ is matched, the match is added to the $2 stack. If that stack isn't empty, we can then match a ], removing the match from the stack. Otherwise, we can match anything that's not a ] (the [ was already matched earlier). The match stops when it meets the matching ] for the [, since the $2 stack is (now) empty at that point.


The substiution consists of two variables separated by a comma. The . indicates that the length of the variable, rather than its value, be used. The > indicates that the variable should be evaluated in terms of the right-hand separator rather than the match. The $` variable refers to the prefix of the match, which means $.` gives the position of the [; the > modifier alters this to the prefix of the match's right separator, which gives the position of the matching ].


Jelly,  22 21 20  19 bytes

No doubt it is possible in Jelly in half this byte count :p ...


A monadic link accepting a list of characters which returns a list of lists of integers.
As a full program it accepts a string and prints a representation of said list.

Try it online!


n€Ø[ḅ-µMịÄÐƤi€0ĖƊ’Ä - Link: list of characters    e.g. "[f[o]o!]"
  Ø[                - list of characters = ['[', ']']
n€                  - not equal? for €ach              [[0,1],[1,1],[0,1],[1,1],[1,0],[1,1],[1,1],[1,0]]
                    -     ...relating to the characters:  [     f     [     o     ]     o     !     ]
    ḅ-              - convert from base -1             [1,0,1,0,-1,0,0,-1]
                    -     ...i.e.: 1 where '['; -1 where ']'; and 0 elsewhere
      µ             - start a new monadic chain with that as the argument, say V
                Ɗ   - last 3 links as a monad (function of V):
          ÐƤ        -   for post-fixes:
         Ä          -     cumulative sum               [[1,1,2,2,1,1,1,0],[0,1,1,0,0,0,-1],[1,1,0,0,0,-1],[0,-1,-1,-1,-2],[-1,-1,-1,-2],[0,0,-1],[0,-1],-1]
            i€0     -   1st index of 0 in €ach (or 0)  [8,1,3,1,0,1,1,0]
               Ė    -   enumerate                      [[1,8],[2,1],[3,3],[4,1],[5,0],[6,1],[7,1],[8,0]]
       M            - maximal indices of V             [1,3]
        ị           - index into                       [[1,8],[3,3]]
                 ’  - decrement                        [[0,7],[2,2]]
                  Ä - cumulative sum (vectorises)      [[0,7],[2,4]]
  • \$\begingroup\$ I was trying to use œ¿ and it's relatives but couldn't find a solution. This was closest I got. \$\endgroup\$
    – dylnan
    Commented Jun 7, 2018 at 19:47
  • \$\begingroup\$ Yes, it can be shorter, but I only managed one measly byte, not half the bytes. It still feels too long. :( \$\endgroup\$ Commented Jun 7, 2018 at 20:04
  • \$\begingroup\$ @EriktheOutgolfer there was an easy 1-byte save here too \$\endgroup\$ Commented Jun 7, 2018 at 20:45

SWI-Prolog 254 bytes

d([']'|T],I,[S|Z],M,R):-J is I+1,d(T,J,Z,[',','(',S,',',I,')'|M],R).
d(['['|T],I,S,M,R):-J is I+1,d(T,J,[I|S],M,R).
d([_|T],I,S,M,R):-J is I+1,d(T,J,S,M,R).


?- m('!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][]').

C (gcc), 87 bytes


Try it online!


To keep track of opening bracket's string indices, the input string is overwritten and used as a stack.

f(char*Z){          // take mutable input string
 for(char*z=Z,*q=z; // copy pointer to current string index, current stack index
 *z;                // loop through the entire string
 *z++-93||          // if z == ']'
   printf("%d,%d;", // decrement stack pointer,
    *--q,z-1-Z))    //  write bracket pair position
  *z-91||           // if z == '['
   (*q++=z-Z);}     // write bracket position onto stack, increment stack pointer

Try it online!


Jelly, 20 bytes


Try it online!

It has a side-effect on the register, hope it's allowed to be a function.

  • \$\begingroup\$ It's reusable, so I think it's fine. BF answers don't typically leave the tape blank \$\endgroup\$
    – dylnan
    Commented Jun 7, 2018 at 20:48

Japt v1.4.5, 23 bytes


Try it online!

Unpacked & How it works


;                              Use alternative set of initial variables
                               A = [] is used here
 UmDE{                         Map over each char of input string...
      D==']?                     If the char is closing bracket...
            ApENo)                 Push the current index and N.pop() to A
                  :D=='[&&       Otherwise, if the char is opening bracket...
                          NpE      Push the current index to N

A     Output A

The output is a flattened array of [closing index, opening index]. If the reversed order is not desired, adding w at the end does the job (+1 bytes).


Common Lisp, 95 bytes

(lambda(u &aux s)(dotimes(p(length u))(case(elt u p)(#\[(push p s))(#\](print`(,(pop s),p))))))
Long version
(defun par (string &aux stack)
  (dotimes (pos (length string))
    (case (char string pos)
      (#\[ (push pos stack))
      (#\] (print (list (pop stack) pos))))))
((lambda(u &aux s)(dotimes(p(length u))(case(elt u p)(#\[(push p s))(#\](print`(,(pop s),p))))))
 "!^45sdfd[hello world[[djfut]%%357]sr[jf]s][srtdg][] ")


(21 27) 
(20 33) 
(36 39) 
(8 41) 
(42 48) 
(49 50)

K (ngn/k), 38 37 bytes

{b@0N 2#,/=(|':+\-/a)b:&|/a:"[]"=\:x}

Try it online!

{ } function with argument x

"[]"=\:x two boolean lists for the occurrences of "[" and "]"

a: assign to a

|/ boolean "or" of the two lists

& where (at which indices) are the brackets?

b: assign to b

-/ a list with 1 for "[", -1 for "]", and 0 everywhere else

+\ partial sums

|': pairwise maxima (each element max'ed with the previous one, the initial element remains the same)

This represents bracket depth for each character. We index it with b (juxtaposition is indexing) and get bracket depth only for the brackets.

= "group by" - a dictionary mapping depths to the indices at which they occur

,/ concatenate the values in the dictionary, ignoring the keys

0N 2# reshape to a 2-column matrix (list of lists)

b@ index b with each element of the matrix


Charcoal, 20 bytes


Try it online! Link is to verbose version of code. Explanation:


Loop over the implicit range of the length of the input string.


Switch on the current character.


If it's a [ then push the current index to the predefined array variable.


If it's a ] then pop the latest index from the array variable and print it and the current index separated by a comma and start a new line. Alternate output formats, if acceptable, would save some bytes: ]I⟦⊟υιω saves 2 bytes but prints each index on a separate line, double-spacing the pairs of indexes; ]I⟦⊟υι simply prints the indexes on separate lines, making it hard to distinguish them.


CJam, 25 bytes

0q{"[]"#"_ \p_p "S/=~)}/;

Surprisingly competitive - loses only to Japt and Jelly [Edit: and Charcoal and Stax :(]

Try it online!


0                          Push 0.
 q                         Push the input.
  {                   }/   For each character in the input:
   "[]"#                     Find index of this character in the string "[]" (or -1 if not found).
                   =         Use this index to choose
        "       "S/            one of the following snippets
                    ~          and execute it:
         _                       If it was 0 ('['), duplicate the number on the stack.
           \p_p                  If it was 1 (']'), print the current number and the one under it.
                                 If it was -1, do nothing.
                     )       Increment the number on top of the stack.
                        ;  Delete the number.

Python 2, 109 bytes

def a(s,r=[],i=0):
 while i<len(s):exec["r+=[i]","o+=[(r.pop(),i)]",'']['[]'.find(s[i])];i+=1
 return o

Try it online!


Pyth,  28  26 bytes


Test suite.

At the moment it's longer than Mnemonic's approach, but I feel like I can golf this down a little and this fortunately also doesn't use Pythonically-imperative structures like V. The initial version was 36 bytes and also had numerous bugs.

How it works

{I#.e,t+lhfSI/LT`Y+._>Qk\] – Full program. Takes a quoted string Q from STDIN.
   .e                      – Enumerated map. k = iteration index, b = current element.
                     >Qk   – Get the elements of Q at indices greater than k.
                   ._      – Generates all the prefixes of this.
                  +     \] – And append an "]" (for handling some edge-cases).
          f                – Filter over this list, with T = current element.
              L `Y             – For each character in str([]), "[]"...
             / T               – ... Count the occurrences of it in T.
           SI                  – And check if the values are sorted increasingly.
         h                 – Head. Retrieve the first element.
       +l                  – Get the length of this + k.
      t                    – Decrement (by 1).
     ,                     – And pair this value with k. Returns [i, k] where i is 
                             the index of the corresponding ] and k is that of [.
  #                        – Filter this list by:
{I                             – The pair is invariant over deduplicating.
  • \$\begingroup\$ {I#.e,t+lhfSI/LT`Y._>Q aaalmost works for 22 bytes... \$\endgroup\$
    – Mr. Xcoder
    Commented Jun 7, 2018 at 17:45

Perl 5, 53 bytes

say"$-[0] ".($+[0]-1)while s/\[[^][]*\]/1x length$&/e

Run as perl -nE '<above code snippet>'. Takes input through stdin.

As usual, the optimal Perl solution to the problem is a regular expression. We attempt to match any pair of brackets which does not contain any pairs within it using a rather silly-looking character class (s/\[[^][]*\]/.../). If the match is successful, we replace the matched text with the digit 1 over and over again so that we don't accidentally match those brackets again, and we print out the indices of the match. Rinse and repeat.


Stax, 13 bytes


Run and debug it

It uses the input stack to track open brace pairs. Here's the program unpacked, ungolfed, and commented.

F       iterate over input characters
 .][I   get the index of the character in the string "[]", or -1
 ^|cv   skip the rest of this iteration if index was -1
 i~     push the current iteration index to the input stack
 C      skip the rest of this iteration if index was 0
 \      form a pair with the top two items from the input stack
 JP     join with space, and print

Run this one


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.