Stacks Interview Questions and Answers

A stack is a recursive data structure, so it's: a stack is either empty or it consists of a top and the rest which is a stack by itself;

A Stack is a container of objects that are inserted and removed according to the last-in first-out (LIFO) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. There are basically three operations that can be performed on stacks. They are:

1. inserting an item into a stack (push).
2. deleting an item from the stack (pop).
3. displaying the contents of the stack (peek or top). A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top.

You can simulate a linked list by using two stacks. One stack is the "list," and the other is used for temporary storage. To add an item at the head, simply push the item onto the stack. To remove from the head, pop from the stack. To insert into the middle somewhere, pop items from the "list" stack and push them onto the temporary stack until you get to your insertion point. Push the new item onto the "list" stack, then pop from the temporary stack and push back onto the "list" stack. Deletion of an arbitrary node is similar. This isn't terribly efficient, by the way, but it would in fact work.

O(
1) . Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they
are both O(1) .
Stack contains 1,2,3:
[1]->[2]->[3]
Push 5:
[5]->[1]->[2]->[3]
Pop:
[1]->[2]->[3]
// returning 5

Because they help manage your data in more a particular way than arrays and lists. It means that when you're debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants. Arrays and lists are random access. They are very flexible and also easily corruptible. If you want to manage your data as FIFO or LIFO it's best to use those, already implemented, collections. More practically you should: Use a queue when you want to get things out in the order that you put them in (FIFO) Use a stack when you want to get things out in the reverse order than you put them in (LIFO) Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed).

The followings are the steps to reversing a String using Stack:

1. String to char[] .
2. Create a Stack .
3. Push all characters, one by one.
4. Then Pop all characters, one by one and put into the char[] .
5. Finally, convert to the String . Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Implementation: Java public static String reverse(String str) {

char[] charArr = str.toCharArray();
int size = charArr.length;
Stack stack = new Stack(size);
int i;
for (i = 0; i < size; ++i) {
  stack.push(charArr[i]);
}
for (i = 0; i < size; ++i) {
  charArr[i] = stack.pop();
}
return String.valueOf(charArr);
}

You can simulate a linked list by using two stacks. One stack is the "list," and the other is used for temporary storage. To add an item at the head, simply push the item onto the stack. To remove from the head, pop from the stack. To insert into the middle somewhere, pop items from the "list" stack and push them onto the temporary stack until you get to your insertion point. Push the new item onto the "list" stack, then pop from the temporary stack and push back onto the "list" stack. Deletion of an arbitrary node is similar.

This isn't terribly efficient, by the way, but it would in fact work.

O(
1) . Note, you don't have to insert at the end of the list. If you insert at the front of a (singly-linked) list, they
are both O(1) .
Stack contains 1,2,3:
[1]->[2]->[3]
Push 5:
[5]->[1]->[2]->[3]
Pop:
[1]->[2]->[3]
// returning 5

They’re very useful because they afford you constant time

O(
1) operations when

inserting or removing from the front of a data structure. One common use of a stack is in compilers, where a stack can be used to make sure that the brackets and parentheses in a code file are all balanced, i.e., have an opening and closing counterpart. Stacks are also very useful in evaluating mathematical expressions.

The followings are the steps to reversing a String using Stack:

1. String to char[] .
2. Create a Stack .
3. Push all characters, one by one.
4. Then Pop all characters, one by one and put into the char[] .
5. Finally, convert to the String .

Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) Implementation: Java public static String reverse(String str) {

char[] charArr = str.toCharArray();
int size = charArr.length;
Stack stack = new Stack(size);
int i;
for (i = 0; i < size; ++i) {
  stack.push(charArr[i]);
}
for (i = 0; i < size; ++i) {
  charArr[i] = stack.pop();
}
return String.valueOf(charArr);
}

If you have an ADT Queue with only push_front() and pop_back() as its interface, there is no way to use it as a stack. A queue is normally a FIFO container, while a stack is LIFO. This means that you cannot just copy the data in sequential order from your queue to your stack, since that will make the elements appear in the "wrong" order. If

you merely want to copy the data from the queue onto a stack, then you need to reverse the data first, which is impossible without allocating memory for all the elements in the queue, if your queue has only that interface mentioned above. There is no good way (performance wise) to reverse a queue. A queue is a one-way container, internally an element only has to know about the next element in line, not about the previous one. This means that you cannot iterate through the queue starting at the back, and that iteration always is

O(
n) .

If you have access to the internals of the queue, then its a trivial question, you can reverse the data in place.

If you have an ADT Queue with only push_front() and pop_back() as its interface, there is no way to use it as a stack. A queue is normally a FIFO container, while a stack is LIFO. This means that you cannot just copy the data in sequential order from your queue to your stack, since that will make the elements appear in the "wrong" order. If you merely want to copy the data from the queue onto a stack, then you need to reverse the data first, which is impossible without allocating memory for all the elements in the queue, if your queue has only that interface mentioned above. There is no good way (performance wise) to reverse a queue. A queue is a one-way container, internally an element only has to know about the next element in line, not about the previous one. This means that you cannot iterate through the queue starting at the back, and that iteration always is

O(
n) .

If you have access to the internals of the queue, then its a trivial question, you can reverse the data in place.

Problem

For example I have a string 2*(1+(2*1)); How to convert this into a binary expression tree?

*
| \
| \
2 +
|\
1 *
|\
2 1

### Solution

Convert infix to postfix or prefix The postfix input is: a b + c d e +**

1. Consider first character if it is not symbol then create node add it to stack
2. If character is symbol then create node with symbol, pop elements and add to left and right of symbol
3. Push symbol node in to the stack.
4. Repeat 1, 2 and 3 till iterator has no more elements Implementation: Java

public Tree.TreeNode createExpressionTree() {
  Iterator <Character> itr = postOrder.iterator();
  Tree tree = new Tree();
  NodeStack nodeStack = new NodeStack();
  Tree.TreeNode node;
  while (itr.hasNext()) {
    Character c = itr.next();
    if (!isDigit(c)) {
      node = tree.createNode(c);
      node.right = nodeStack.pop();
      node.left = nodeStack.pop();
      nodeStack.push(node);
    } else {
      node = tree.creteNode(c);
      nodeStack.push(node);
    }
}
node = nodeStack.pop();
return node;
}

Infix notation is easy to read for humans, whereas pre-/postfix notation is easier to parse for a machine. The big advantage in pre-/postfix notation is that there never arise any questions like operator precedence. For example, consider the infix expression 1 # 2 $ 3 . Now, we don't know what those operators mean, so there are two possible corresponding postfix expressions: 1 2 # 3 $ and 1 2 3 $ # . Without knowing the rules governing the use of these operators, the infix expression is essentially worthless. Also. in case of infix expression , the time required for evaluation is

O(
n2) . The reason is precedence of

operators. Ex : a+bc . In this we won't directly evaluate a+b . First we traverse the entire expression and find the operator having highest precedence . In our case it is * , thus first we evaluate bc and thus again follow the same procedure again , till we complete evaluate the expression. But this is not so in case of postfix or prefix expression. The time required for evaluation of postfix expression is

O(n) .

Problem

I know how to do that with 2 stacks but how to implement it with one?

Solution

Tricky question. You can "cheat" by using recursive function calls to pop the stack, then you push the item being queued, then as the recursive calls unwind you push what was popped. But this is really two stacks, because the function call stack counter is a stack. Following is the implementation: During Enqueue operation, we can straight away push the element into the stack. During Dequeue operation, Pop all the elements from a Stack recursively until Stack size is equal to 1 . If Stack size = 1 , Pop item from Stack, and return the same item. Push all popped element back to Stack. Implementation: Java

public class QueueUsingSingleStack {
  Stack<Integer> stack = new Stack<>();
  private void enqueue(int i) {
    stack.push(i);

  }
private int dequeue() throws Exception {
  if (stack.size() == 0)
  throw new Exception("Queue is Empty");
  if (stack.size() == 1)
  return stack.pop();
  int data = stack.pop();
  int retVal = dequeue();
  stack.push(data);
  return retVal;
}
public static void main(String[] args) throws Exception {
  QueueUsingSingleStack queue = new QueueUsingSingleStack();
  queue.enqueue(10);
  queue.enqueue(20);
  queue.enqueue(30);
  queue.enqueue(40);
  System.out.println(queue.dequeue());
  System.out.println(queue.dequeue());
  System.out.println(queue.dequeue());
  System.out.println(queue.dequeue());
}
}

Infix notation is easy to read for humans, whereas pre-/postfix notation is easier to parse for a machine. The big advantage in pre-/postfix notation is that there never arise any questions like operator precedence. For example, consider the infix expression 1 # 2 $ 3 . Now, we don't know what those operators mean, so there are two possible corresponding postfix expressions: 1 2 # 3 $ and 1 2 3 $ # . Without knowing the rules governing the use of these operators, the infix expression is essentially worthless. Also. in case of infix expression , the time required for evaluation is

O(
n2) . The reason is precedence of

operators. Ex : a+bc . In this we won't directly evaluate a+b . First we traverse the entire expression and find the operator having highest precedence . In our case it is * , thus first we evaluate bc and thus again follow the same procedure again , till we complete evaluate the expression. But this is not so in case of postfix or prefix expression. The time required for evaluation of postfix expression is

O(n) .

The following implementations are most common: Stack backed by a singly-linked list. Because a singly-linked list supports

O(
1) time prepend and delete-

first, the cost to push or pop into a linked-list-backed stack is also

O(
1) worst-case. However, each new

element added requires a new allocation, and allocations can be expensive compared to other operations. The locality of the linked list is not as good as the locality of the dynamic array since there is no guarantee that the linked list cells will be stored contiguously in memory. Stack backed by a dynamic array. Pushing onto the stack can be implemented by appending a new element to the dynamic array, which takes amortised

O(
1) time and worst-case
O(
n) time. Popping from

the stack can be implemented by just removing the last element, which runs in worst-case

O(
1) (or
amortised
O(
1) if you want to try to reclaim unused space). In other words, the most common
implementation has best-case
O(
1) push and pop, worst-case
O(
n) push and
O(
1) pop, and amortised
O(
1) push and
O(
1) pop.

With

O(
n) extra space it is trivial. A simple solution for reversing a stack is to create another stack. Pop

elements from the old stack into the new stack and we will have the reversed contents in the new stack. Without extra space, you need recursion to hold values. The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

1. The reverse() function checks whether the stack is empty or not. If the stack is not empty, we pop the top element and store it in temp variable. We then call reverse() function again (first recursion) on the updated stack. When this child function returns, we call the helper function insertAtBottom() . The base case for this recursive function is:

if s.isEmpty(stack) : return
2. The insertAtBottom() function (second recursion) recursively inserts an element at the
bottom of a stack. If

the stack is empty, it simply pushes the item else, it pops the top element and stores in the temp variable. Then call the function again on the updated stack. When this child function returns it pushes temp back in the stack. Complexity Analysis: Time Complexity: O(n^2) Space Complexity: O(n^2) We are using two functions in which first function is calling itself recursively as well as the second function in each call. Also the second function is calling itself recursively, so Time complexity is

O(
n2) .
We are storing both the functions in call stack one after another, so Space complexity is O(2n) =
O(
n) .
Implementation:
Java
public void reverse(Stack < Integer > stack) {
  if (stack.isEmpty() == false) {
    //pop out all the items from the stack and store it in function stack
    int x = stack.pop();
    reverse(stack);
    //now insert the items into stack in reversed order
    //last item popped from the stack
    insert_at_bottom(stack, x);
  }
}
public void insert_at_bottom(Stack < Integer > stack, int x) {//check if stack is empty
  if (stack.isEmpty()) {
    stack.push(x);

    return;
  }
//take out the existing items in stack and keep it in function stack
int y = stack.pop();
//push x to the bottom
insert_at_bottom(stack, x);//push back all the items from function stack to stack
stack.push(y);
}
PY

#Recursive function to insert at bottom of the stack def insertatbottom(stack,item):

if isempty(stack):
push(stack,item)
else:
temp=pop(stack)
insertatbottom(stack,item)
push(stack,temp)#Recursive function to reverse stack using insertatbottom
def reverse(stack):
if not isempty(stack):
temp=pop(stack)
reverse(stack)
insertatbottom(stack,temp)#function to create a stack.It intializes stack size as 0
def createstack():
stack=[]

return stack#Function to check if stack is empty def isempty(stack): return len(stack)==0:#function to push an element onto the stack def push(stack,item):

stack.append(item)#Function to pop an element from the stack
def pop(stack):
if isempty(stack):

return -1 return stack.pop()

Imagine all items are organized into two stacks, draw them facing each other where face is where you put and peek: 1,2,3,4-><-5,6,7,8 now you can move 4 to 5: 1,2,3-><-4,5,6,7,8 and 3 to 4: 1,2-><-3,4,5,6,7,8 and you can go backwards. You may also need another two stacks so that you can traverse List via the tail: 1,2,3,4 -> <-5,6,7,8 // first pair of stacks 8,7,6,5 -> <-4,3,2,1 // second pair of stacks kept in reverse order once current stack runs out empty-><-1,2,3,4,5,6,7,8 // first pair of stacks is currently being traversed empty-><-8,7,6,5,4,3,2,1 // second pair of stacks simply switch to the second pair of stacks! Implementation: Java

import java.util.Stack;
class DoubleLinkedList{
  Stack<Integer> s;
  Stack<Integer> t;
  int count;
  DoubleLinkedList(){
    s = new Stack<Integer>();
    t = new Stack<Integer>();
    count = 0;
  }
public void insertInBeginning(int data){

  while(!s.isEmpty()){
    t.push(s.pop());
  }
s.push(data);
count++;
}
public void insertAtEnd(int data){
  while(!t.isEmpty()){
    s.push(t.pop());
  }
t.push(data);
count++;
}
public void moveForward(){
  while(!t.isEmpty()){
    int temp = t.pop();
    System.out.println(temp);
    s.push(temp);
  }
}
public void moveBackward(){
  while(!s.isEmpty()){
    int temp = s.pop();
    System.out.println(temp);
    t.push(temp);
  }
}
public void delete(int data){
  while(!s.isEmpty()){
    t.push(s.pop());
  }
while(!t.isEmpty()){
  if(t.peek() == data){
    t.pop();
    return;
  }
else{
  s.push(t.pop());
}
}
}
public void deleteFirst(){
  while(!s.isEmpty()){
    int temp = s.pop();
    if(s.peek() == null){
      return;
    }
  t.push(temp);
}
}
public void deleteLast(){
  while(!t.isEmpty()){
    int temp = t.pop();
    if(t.peek() == null){
      return;
    }
  s.push(temp);
}
}
}

Infix expression notation requires that the operators appear between them in the expression A + B A + B * C Prefix expression notation requires that all operators precede the two operands that they work on.

• A B
• A * B C Postfix, on the other hand, requires that its operators come after the corresponding operands. A B + A B C * + Note: Only infix notation requires the additional symbols like () to determine the order of operations . The order of operations within prefix and postfix expressions is completely determined by the position of the operator and nothing else. In many ways, this makes infix the least desirable notation to use. Infix notation is easy to read for humans, whereas pre-postfix notation is easier to parse for a machine.

A stack performs push and pop operations. So, the push and pop operations are carried out between theinput_stack and the auxilary_stack in such a way that the auxiliary stack contains the sorted input stack. Solution Steps:

1. Create a temporary stack say aux_stack.
2. Repeat until the input_stack is not empty
3. Pop an element from input_stack call it temp_value.
4. While aux_stack is not empty and top of the aux_stack < temp_value, pop data from aux_stack and push it to the input_stack
5. Push temp_value to the aux_stack
6. return the aux_stack. Implementation: Java Stack sort_stack(Stack input_stack) { Stack aux_stack

while(!input_stack.empty())
{
  int temp_value = input_stack.top()
  input_stack.pop()
  while(!aux_stack.empty() and aux_stack.top() > temp) {

    input_stack.push(aux_stack.top())
    aux_stack.pop()
  }
aux_stack.push(temp_value)
}

return aux_stack

}
PY
# Sort using insertion sort with stacks O(n^2)
def sort_stack(l):
res_stack = deque()# We keep res_stack always sorted
while len(l) > 0:
current = l.pop()
while True:
if len(res_stack) == 0:
res_stack.append(current)
break
elem = res_stack.pop()
if elem <= current:
res_stack.append(elem)
res_stack.append(current)
break
else:
l.append(elem)

return res_stack

With

O(
n) extra space it is trivial. A simple solution for reversing a stack is to create another stack. Pop

elements from the old stack into the new stack and we will have the reversed contents in the new stack. Without extra space, you need recursion to hold values. The idea of the solution is to hold all values in Function Call Stack until the stack becomes empty. When the stack becomes empty, insert all held items one by one at the bottom of the stack.

1. The reverse() function checks whether the stack is empty or not. If the stack is not empty, we pop the top element and store it in temp variable. We then call reverse() function again (first recursion) on the updated stack. When this child function returns, we call the helper function insertAtBottom() .

The base case for this recursive function is:

if s.isEmpty(stack) : return
2. The insertAtBottom() function (second recursion) recursively inserts an element at the
bottom of a stack. If

the stack is empty, it simply pushes the item else, it pops the top element and stores in the temp variable. Then call the function again on the updated stack. When this child function returns it pushes temp back in the stack. Complexity Analysis: Time Complexity: O(n^2) Space Complexity: O(n^2) We are using two functions in which first function is calling itself recursively as well as the second function in each call. Also the second function is calling itself recursively, so Time complexity is

O(
n2) .
We are storing both the functions in call stack one after another, so Space complexity is O(2n) =
O(
n) .
Implementation:
Java
public void reverse(Stack < Integer > stack) {
  if (stack.isEmpty() == false) {
    //pop out all the items from the stack and store it in function stack
    int x = stack.pop();
    reverse(stack);
    //now insert the items into stack in reversed order
    //last item popped from the stack
    insert_at_bottom(stack, x);
  }
}
public void insert_at_bottom(Stack < Integer > stack, int x) {//check if stack is empty
  if (stack.isEmpty()) {
    stack.push(x);
    return;
  }
//take out the existing items in stack and keep it in function stack
int y = stack.pop();
//push x to the bottom
insert_at_bottom(stack, x);//push back all the items from function stack to stack
stack.push(y);
}
PY

#Recursive function to insert at bottom of the stack def insertatbottom(stack,item):

if isempty(stack):
push(stack,item)
else:
temp=pop(stack)
insertatbottom(stack,item)

push(stack,temp)#Recursive function to reverse stack using insertatbottom
def reverse(stack):
if not isempty(stack):
temp=pop(stack)
reverse(stack)
insertatbottom(stack,temp)#function to create a stack.It intializes stack size as 0
def createstack():
stack=[]

return stack#Function to check if stack is empty def isempty(stack): return len(stack)==0:#function to push an element onto the stack def push(stack,item):

stack.append(item)#Function to pop an element from the stack
def pop(stack):
if isempty(stack):

return -1 return stack.pop()

One of the most important applications of stacks is to check if the parentheses are balanced in a given expression. The compiler generates an error if the parentheses are not matched. Here are some of the balanced and unbalanced expressions: balanced parentheses Algorithm

1. Declare a character stack which will hold an array of all the opening parenthesis.
2. Now traverse the expression string exp.
3. If the current character is a starting bracket ( ( or { or [ ) then push it to stack.
4. If the current character is a closing bracket ( ) or } or ] ) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
5. After complete traversal, if there is some starting bracket left in stack then “not balanced” Complexity Analysis: Time Complexity: O(n) Space Complexity: O(n) We are traversing through each character of string, Time complexity

O(
n) .

We are storing the opposite parentheses characters in the stack, in the worst case there can be all the opposite characters in the string, Space complexity

O(
n) .
Implementation:
JS

let isMatchingBrackets = function (str) {
  let stack = [];
  let map = {
    '(': ')',
    '[': ']',
    '{': '}'
  }
for (let i = 0; i < str.length; i++) {
  // If character is an opening brace add it to a stack
  if (str[i] === '(' || str[i] === '{' || str[i] === '[' ) {
      stack.push(str[i]);
    }
  // If that character is a closing brace, pop from the stack, which will also reduce the length

of the stack each time a closing bracket is encountered.

else {
  let last = stack.pop();
  //If the popped element from the stack, which is the last opening brace doesn’t match the

corresponding closing brace in the map, then return false

if (str[i] !== map[last]) {return false};
}
}
// By the completion of the for loop after checking all the brackets of the str, at the end, if the

stack is not empty then fail

if (stack.length !== 0) {return false};
return true;
}
Java
public static boolean balancedParenthensies(String s) {
  Stack<Character> stack = new Stack<Character>();
  for(int i = 0; i < s.length(); i++) {
    char c = s.charAt(i);
    if(c == '[' || c == '(' || c == '{' ) {
        stack.push(c);
      } else if(c == ']') {
        if(stack.isEmpty() || stack.pop() != '[') {
          return false;
        }
    } else if(c == ')') {
      if(stack.isEmpty() || stack.pop() != '(') {
        return false;
      }
  } else if(c == '}') {
if(stack.isEmpty() || stack.pop() != '{') {
    return false;
  }
}
}
return stack.isEmpty();
}
PY
open_list = ["[","{","("]
  close_list = ["]","}",")"]# Function to check parentheses
def check(myStr):
stack = []
for i in myStr:

if i in open_list:
stack.append(i)
elif i in close_list:
pos = close_list.index(i)
if ((len(stack) > 0) and
(open_list[pos] == stack[len(stack)-1])):
stack.pop()
else:

return "Unbalanced"

if len(stack) == 0:

return "Balanced" else: return "Unbalanced"

The following implementations are most common: Stack backed by a singly-linked list. Because a singly-linked list supports

O(
1) time prepend and delete-

first, the cost to push or pop into a linked-list-backed stack is also

O(
1) worst-case. However, each new

element added requires a new allocation, and allocations can be expensive compared to other operations. The locality of the linked list is not as good as the locality of the dynamic array since there is no guarantee that the linked list cells will be stored contiguously in memory. Stack backed by a dynamic array. Pushing onto the stack can be implemented by appending a new element to the dynamic array, which takes amortised

O(
1) time and worst-case
O(
n) time. Popping from

the stack can be implemented by just removing the last element, which runs in worst-case

O(
1) (or
amortised
O(
1) if you want to try to reclaim unused space). In other words, the most common
implementation has best-case
O(
1) push and pop, worst-case
O(
n) push and
O(
1) pop, and amortised
O(
1) push and
O(
1) pop.

Problem

There is a large file( 1TB) containing braces. How to check for braces balance? Make this process parallel.

Solution

If ( = 1 and ) = -1 . We should check the same two conditions:

1. The total sum of the brackets is 0
2. We never go negative at any point of time.

int counter = 0;
for (int i=0; i<string.Length; i++)
{
  char c = string[i];
  if (c == '{')
    {
      counter++;
    }
  else if (c == '}')
{
  counter--;
  if (counter < 0)
  {
    return false;
  }
}
}
return (counter == 0);

The first instinct to solving the parallel problem might be to split the work up into equal-sized chunks for each processor. If there are N characters in the file and K processors, give each processor a chunk of N/K characters. When processing a chunk, we can no longer simply return false when the count drops below 0, because there may be more opening braces in an earlier chunk processed by a different processor. We also can't return false if the counter is not 0 at the end, because it may be that there are more closing braces in later chunks. What we should calculate for each chunk, instead, is:

1. If we were doing a global brace counter as in the single-threaded approach, by how much would this chunk change the counter? This can be a positive or negative number. Call this the " brace delta". This number is equal to the number of opening braces minus the number of closing braces in the chunk.
2. While we are calculating the " brace delta", what is the lowest point to which the brace delta drops anytime during the processing of the chunk? Call that the " brace delta minimum". This number is important because this is the point in the chunk where the global counter would be the smallest. We can check whether the global counter would have ever been negative by seeing whether (global counter before chunk) + (brace delta minimum in chunk) < 0 for any chunk. These two things would be calculated by: ChunkResult BraceDeltaAlgorithm (int chunkStartPos, int chunkEndPos, String input)

{
  int braceDelta = 0;
  int minBraceDelta = braceDelta;
  for (int i=chunkStartPos; i<chunkEndPos; i++)
  {
    char c = input[i];
    if (c == '{')
      {
        braceDelta++;
      }
    else if (c == '}')
  {
    braceDelta--;
    if (braceDelta < minBraceDelta)
    {
      minBraceDelta = braceDelta;
    }
}
}
return new ChunkResult (braceDelta, minBraceDelta);
}
The complexity of the above code is O(N/K) for each of K processors. However, we can consider it O(N/K) time

because all the processors can work in parallel. After we process each chunk in parallel, we combine the results in a single-threaded way. We use the brace deltas to calculate the value of the global counter at the beginning of every chunk, and we use the brace delta min of the chunks to verify that the global counter never drops below 0. The global counter value should be 0 at the end of all the chunks as before.

int globalCounter = 0;
for (int i=0; i<K; i++)
{
  ChunkResult result = childThreads[i].getResult();
  if ( globalCounter + result.minBraceDelta < 0)
  {
    return false;
  }
globalCounter += result.braceDelta;
}
return (globalCounter == 0);

The non-parallel part takes O(K) time, making the overall time for the solution O(N/K + K) .