Ruby Algorithms

I am a ruby lover,if you too love ruby then this blog is just for you.
After searching resources for learning algorithms and data-structures in ruby when i didn't find any good resource.
So, I took this initiative to build a platform for learning and discussing Algorithms and data-structures in ruby. This blog aims to be a platform where anyone can learn algorithms and data-structures in ruby. Please contribute on Github and share this platform with all other ruby lovers.
The code feautured here can be found on Github.

arrays

Array rotation-II (Juggling Algorithm)

Given an zero indexed array and positive integer d,rotate the array by d-steps to the left.

Array rotation-III (Reversal Algorithm)

Given an zero indexed array and positive integer d,rotate the array by d-steps to the left.

Array rotation-IV (Block Swap Algorithm)

Given an zero indexed array and positive integer d,rotate the array by d-steps to the left.

Array rotation-I

Given an zero indexed array and positive integer d,rotate the array by d-steps to the left.

Segregate 0s on left side and 1s on right side in given array

Given an array of 0s and 1s in random order.Segregate 0s on left side and 1s on right side of the array. Brute-force: Count 0s and rewrite array first with c...

Segregate and put all 0s first, then all 1s and all 2s in last

Given an array A[] consisting 0s, 1s and 2s, put all 0s first, then all 1s and all 2s in last. Brute-force: Count 0s and 1s (using 2 varibales)and rewrite ar...

Equilibrium Index in an array

Given an zero indexed unsorted array find(if exists) the equilibrium index. Equilibrium index of an array is an index such that the sum of elements at lower ...

Leaders in an array

Given an zero indexed unsorted array find(if exist) the leaders in an array. An element is leader if it is greater than all the elements to its right side,th...

Majority Element in an Array

Find majority element(if exists) in a given array.

Maximum j – i such that arr[j] > arr[i].

Given an array arr[], find the maximum j – i such that arr[j] > arr[i].

Maximum sum with no two adjacent elements

Given an array of positive numbers,find the maximum possible sum such that no two chosen numbers are adjacent

Median of two sorted arrays

ere are 2 sorted arrays A and B of size n each. find the median of the array obtained after merging the above 2 arrays(i.e. array of length 2n). e.g. [[1,2,3...

Move all zeros to end

Given an array of random numbers, Push all the zero’s of a given array to the end of the array Algorithm

Pair with sum equal to given value

Given an array A[] and a number x, check for pair in A[] with sum as x

Print 2D-array in spiral order

Given a matrix(2D array),print all of its elements in spiral order. e.g. [[1,2,3].[4,,5,6],[7,8,9]] => 1 2 3 6 9 8 7 4 5

Create a product array from a given array

Given an array ‘a’,create a product array where product[i]==product of all elements except a[i] Time-complexity: O(n) Space-complexity: O(n){for product arra...

Replace every element by product of previous and next

Given an array replace every element by product of previous and next Note: first element is replaced by product of first and second and last element by produ...

Reverse an array

Given a zero index array reverse the order of elements

Shuffling an array

Knuth Shuffling Algorithm Choose random number between i and n-i and swap

Smallest and second smallest in an array

Given an array of elements,Find the smallest and second smallest element.

Swapping two elements

Method 1 (using temporary variable)

Union And Intersection of two arrays

Given two sorted arrays ,Print the elements in the union and intersection of these arrays Time-complexity:O(n+m)(n=length of array1 and m=length of array2) A...

bitAlgos

Check if a given number is even or odd

Given a number,check if it is even or odd using bit operations. Algorithm: let num be x find x&1 ,if result is 0 then even else odd. The Least sign...

Check if a given number is power of two

Given a number,check if it is power of 2 or not without using division or modulo operator.

Count number of set bits in binary notation

Given a number “n”,count the number of set bits in it. Algorithm(Brian Kernighan’s method): 1. set count=0 2. while n>0 set n:=n&(n-1) incre...

Unset the least significant bit

Given a binary number unset the rightmost set bit. Algorithm: The biwise “&” of any number n with n-1 unsets the rightmost set bit e.g. 5=101 ,5-1=4=100 ...

dynamicProgramming

Largest sum continuos subarray

Given a zero index array find the sum of contiguos subarray which has the largest sum. Time-complexity: O(n) Auxiliary space: O(1)

Largest product continuos subarray

Given a zero index array find the product of contiguos subarray which has the largest product. Time-complexity: O(n) Auxiliary space: O(1)

greedyAlgos

linkedlist

mathematics

Finding Square root (Babylonian Method)

Babylonian method for finding square root( based on Newton–Raphson method)

Fast multiplication(Russian Peasant Method)

Given two numbers a and b, write a fast method to multiply both of them. Algorithm: Russian Peasant Method

searching

Binary Search Algorithm

Time Complexity = O(logn) Precondition: List should be sorted

Ubiquitous Binary Search

Binary Search Implementation which can be used in various problems Application of this implimantation: http://www.geeksforgeeks.org/the-ubiquitous-binary-sea...

sorting

3 way Quick Sort Algorithm

Quick sort implementation which can handle duplicates well. Algorithm

Bubble Sort Algorithm

Bubble Sort Implementation (works by repeatedly swapping the adjacent elements if they are in wrong order.) # Time-complexity : O(n^2), In-place, Can be made...

Counting Sort Algorithm

Counting sort is a non comparison-based linear sorting algorithm which can be used if the range of elements is known.

Insertion Sort Algorithm

Inserion Sort implementation (stable) Time Complexity: O(n^2),In-place,stable Very useful for sorting nearly sorted array, very fast and effective for sma...

Merge Sort Algorithm

Merge Sort (divides input array in two halves, calls itself for the two halves and then merges the two sorted halves recursively)

Pancake Sort Algorithm

Given an unsorted array , sort the array when with only using the operation flip(a,i).flip(a,i) means reversing the array a from index 0 to i Time-complex...

Quick Sort Algorithm

Time-complexity:: Worst case (array already sorted/reverse sorted or too many duplicates): O(n^2), Average case : O(nlogn), Best case(when partition alway...

Selection Sort Algorithm

Selection Sort Implementation (sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at th...

Shell Sort Algorithm

Shell Sort implementation(Diminishing Increment Sort) Time-complexity: O(n^2), In-place will be using Knuth series :3n+1

Sort array in wave-form

Given an unsorted array of integers, sort the array into a wave like array. An array ‘arr[0..n-1]’ is sorted in wave form if arr[0] >= arr[1] <= arr[2]...