# Tag Archives: datastructures

## Find the median of two sorted arrays

Given two sorted arrays A and B containing N elements each. Give an algorithm to ﬁnd the median of two sorted arrays in O(lgN) time. Ex A={1,2,3} B={1,4,5,6} median=3 . The naive algorithm will be to merge the arrays A and B and return the median .But the time complexity will be O(N) and this… Read More »

## Stack class with Push, Pop, and Min in Constant Time

This is a commonly asked interview question .The problem is like this Design a stack class that supports push, pop, and min ( retrieving the minimum element ) operations in constant time The problem can be solved easily using an extra stack (MinStack) .On each min call you just have to return the element the… Read More »

## Balanced Parentheses Algorithm

This is a classic example of how using an appropriate Datastructure can improve the quality of your algorithm. The Balanced Parentheses or Valid Parentheses is like this : Given a string containing ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid or not. [(a+b)+c] is Valid where as (a+b)+c] is… Read More »

## 3 sum problem or a+b+c=sum

The 3 Sum 🙂 problem is like this : Given an array of integers A, find 3 numbers a,b,c such that they add up to a specific target number s. a+b+c =s The problem is somewhat similar to the two sum problem . Ex Input : A={4,5,1,2,3} s=8 output :5,2,1 We can take different approaches… Read More »

## Two Sum (a+b =s) Problem

The Two Sum problem is like this : Given an array of integers A, find two numbers a,b such that they add up to a specific target number s. a+b =s Though this problem looks simple but this problem forms a kind of base for solving other bigger problems like 3sum problem and 4 sum… Read More »