Skip to content

Instantly share code, notes, and snippets.

View aaani's full-sized avatar

Ani Mishra aaani

View GitHub Profile
@aaani
aaani / QuickSort.java
Last active November 23, 2023 07:56
Here is a Java implementation of randomized quicksort. This is a non-deterministic algorithm with average case time complexity of O(n*log(n)) and worst case space complexity of O(1), where n is the input size. This algorithm is unstable but one can make it stable by giving away O(n) space.
import java.util.*;
/**
*
* @author anirvana
*/
public class QuickSort {
public static void main(String[] args) {
ArrayList<Integer> elements=new ArrayList<Integer>();
body {
background-color: green;
}
body {
background-color: red;
}
pair<pair<char,char>,int> maxLenSubstring2Chars(string s){
pair<char,int> lastChar;
lastChar.first=s[0];
lastChar.second=1;
pair<pair<char,char>,int> longestPairYet;
longestPairYet.second=-1;
pair<pair<char,char>,int> currentPair;
currentPair.first.first=s[0];
#include <iostream>
#include <vector>
using namespace std;
int Max(int a, int b){
return a>b?a:b;
}
int Min(int a, int b){
return a<b?a:b;
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
class SetOfStacks{
vector<stack<int>> stacks;
int threshold;
template<int N>
void rotate90Clockwise(int (&matrix)[N][N]){
//Transpose the matrix
int temp;
for(int i=0;i<N;i++){
for(int j=0;j<i;j++){
temp=matrix[i][j];
matrix[i][j]=matrix[j][i];
matrix[j][i]=temp;
}
int find(vector<int> elements, int start, int end, int key){
if(start>end) return -1;
int mid = start + (end-start)/2;
if(elements[mid]==key) return mid;
if(elements[mid]>=elements[start]){
if(key>=elements[start] && key<elements[mid]) return find(elements,start,mid-1,key);
else return find(elements,mid+1,end,key);
}else{
int LCPLength(vector<string> input){
//Find the length of shortest string in the input set
int minLen = INT32_MAX;
for(int i=0;i<input.size();i++){
if(input[i].length()<minLen) minLen=(int)input[i].length();
}
bool done = false;
int lcpLen=0;
@aaani
aaani / MergeSort.java
Last active December 21, 2015 17:08
Here is a Java implementation of merge sort. This algorithms runs in O(n*log(n)) worst case time and O(n) space, where n is the input size. It's a stable sort, commonly used in sorting from disk.
import java.util.ArrayList;
/**
*
* @author anirvana
*/
public class MergeSort {
public static void main(String[] args) {
ArrayList<Integer> elements=new ArrayList<Integer>();