## Valid or Well Formed Parentheses | Part – 1

Objective: You have been asked to write an algorithm to find Whether Given the Sequence of parentheses is well-formed. This question was asked in the Amazon Interview.

Input: A String contains a sequence of parentheses

Output: true or false on whether parentheses are well-formed or not

Approach:

• Idea is to have two counters, one for open parentheses ‘{‘ and one for close ‘}’
• Read one character at a time and increment one of the counters
• If any given point of time count of close parentheses is greater than the open one, return false
• If at the end both counters are equal, return true

Example: { { } { } } – Well-formed

{ { } { = Not well-formed

Code:

## Find an Element in 2 dimensional sorted array

Objective: Write an algorithm to find an element in 2-dimensional array where rows and columns are sorted respectively.

Input: A two dimensional sorted array, arrA[][].

Output: True or false based on whether the element exists and its location

Approach:

## Find Whether Given String is palindrome or Not.

Objective : Write an algorithm to find Whether Given String is palindrome or Not.

Input:  A String,

Output: true or false on whether string is palindrome or not

Approach:

• Use recursive approach
• Compare first and last characters if they are not same- return false
• If they are same make, remove the first and last characters and make a recursive call.

Example:

```Jain niaJ => compare ‘J’ with ‘J’ =>returns true

ain nia => compare ‘a’ with ‘a’ =>returns true

in ni => compare ‘i’ with ‘i’ =>returns true

n n => compare ‘n’ with ‘n’ =>returns true

string length <2 => returns true```

## Find a peak element in a Given Array

Objective: In this article, we will discuss an algorithm to Find a peak element in a Given Array. We will see the recursion techniques to solve this problem.

Peak Element: peak element is the element that is greater than or equal to both of its neighbors.

Input:  Array, arrA[] .

Output: A peak element and its index

Approach:

A simple approach is to do a linear scan of an array and using a few variables we can find a peak element. But the Time Complexity will be O(n) but real question is, Can we do better?

The answer is yes, by using Binary Search techniques.

## Find two Missing Numbers in a Sequence of Consecutive Numbers

Objective : Write an algorithm to find two Missing Numbers in a Sequence of Consecutive Numbers

Input:  Array, arrA[] with two missing numbers and Range

Output : Two missing numbers

Approach:

• Approach is very simple, Add all the given numbers say S
• Calculate sum of N numbers by formula n(n+1)/2 , say N
• Find sum of two missing numbers a+b = N-S

## Find a Missing Number From a Sequence of Consecutive Numbers

Objective: You have been asked to write an algorithm to Find a Missing Number From a Sequence of Consecutive Numbers

Input:  Array, arrA[] with a missing number and Range

Output: missing number

Approach:

• The approach is very simple, Add all the given numbers say S
• Calculate the sum of N numbers by formula n(n+1)/2, say N
• Find missing number m = N-S

Example : suppose array given is  {1,2,3,4,5,6,8,9,10} and range is 10.