50 leetcode for infosys

BY: coding_errOR1

Find the Largest Element in an Array

Question

Given an array of integers, find the largest element.

Python
def largest_element(arr):
return max(arr)

print(largest_element([1, 8, 7, 56, 90]))

Java
class Main {
static int largest(int[] arr) {
int max = arr[0];
for (int x : arr)
if (x > max) max = x;
return max;
}
}

C++
int largest(vector<int>& arr) {
return *max_element([Link](), [Link]());
}

Second Largest Element

Question

Find the second largest element without sorting.

Python
def second_largest(arr):

BY: coding_error1
 first = second = -1
for x in arr:
if x > first:
second = first
first = x
elif x > second and x != first:
second = x
return second

Java
static int secondLargest(int[] arr) {
int first = -1, second = -1;
for (int x : arr) {
if (x > first) {
second = first;
first = x;
} else if (x > second && x != first) {
second = x;
}
}
return second;
}

C++
int secondLargest(vector<int>& arr) {
int first = -1, second = -1;
for (int x : arr) {
if (x > first) {
second = first;
first = x;
} else if (x > second && x != first) {
second = x;
}
}
return second;
}

Check if Array is Sorted

Question

Check whether the array is sorted in non-decreasing order.

Python
def is_sorted(arr):
return all(arr[i] <= arr[i+1] for i in range(len(arr)-1))

Java
static boolean isSorted(int[] arr) {

BY: coding_error1
 for (int i = 0; i < [Link] - 1; i++)
if (arr[i] > arr[i+1]) return false;
return true;
}

C++
bool isSorted(vector<int>& arr) {
return is_sorted([Link](), [Link]());
}

Remove Duplicates from Sorted Array

Question

Remove duplicates in-place and return new length.

Python
def remove_duplicates(arr):
return len(set(arr))

Java
static int removeDuplicates(int[] arr) {
int i = 0;
for (int j = 1; j < [Link]; j++) {
if (arr[i] != arr[j]) {
i++;
arr[i] = arr[j];
}
}
return i + 1;
}

C++
int removeDuplicates(vector<int>& arr) {
return unique([Link](), [Link]()) - [Link]();
}

Rotate Array by K Positions

Question

Rotate the array to the right by K steps.

Python

BY: coding_error1
def rotate(arr, k):
k %= len(arr)
return arr[-k:] + arr[:-k]

Java
static void rotate(int[] arr, int k) {
k %= [Link];
reverse(arr, 0, [Link] - 1);
reverse(arr, 0, k - 1);
reverse(arr, k, [Link] - 1);
}

C++
void rotate(vector<int>& arr, int k) {
k %= [Link]();
reverse([Link](), [Link]());
reverse([Link](), [Link]() + k);
reverse([Link]() + k, [Link]());
}

Move Zeroes to End

Question

Move all zeroes to the end while maintaining order.

Python
def move_zeroes(arr):
return [x for x in arr if x != 0] + [0]*[Link](0)

Java
static void moveZeroes(int[] arr) {
int j = 0;
for (int i = 0; i < [Link]; i++)
if (arr[i] != 0) arr[j++] = arr[i];
while (j < [Link]) arr[j++] = 0;
}

C++
void moveZeroes(vector<int>& arr) {
int j = 0;
for (int i = 0; i < [Link](); i++)
if (arr[i] != 0) arr[j++] = arr[i];
while (j < [Link]()) arr[j++] = 0;
}

BY: coding_error1
 Maximum Subarray Sum (Kadane)
Question

Find the maximum sum of a contiguous subarray.

Python
def max_subarray(arr):
curr = max_sum = arr[0]
for x in arr[1:]:
curr = max(x, curr + x)
max_sum = max(max_sum, curr)
return max_sum

Java
static int maxSubArray(int[] arr) {
int curr = arr[0], max = arr[0];
for (int i = 1; i < [Link]; i++) {
curr = [Link](arr[i], curr + arr[i]);
max = [Link](max, curr);
}
return max;
}

C++
int maxSubArray(vector<int>& arr) {
int curr = arr[0], maxSum = arr[0];
for (int i = 1; i < [Link](); i++) {
curr = max(arr[i], curr + arr[i]);
maxSum = max(maxSum, curr);
}
return maxSum;
}

Two Sum
Question

Return indices of two numbers whose sum equals target.

Python
def two_sum(nums, target):
mp = {}
for i, n in enumerate(nums):
if target - n in mp:
return [mp[target - n], i]
mp[n] = i

BY: coding_error1
 Java
static int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < [Link]; i++) {
if ([Link](target - nums[i]))
return new int[]{[Link](target - nums[i]), i};
[Link](nums[i], i);
}
return new int[]{};
}

C++
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for (int i = 0; i < [Link](); i++) {
if ([Link](target - nums[i]))
return {mp[target - nums[i]], i};
mp[nums[i]] = i;
}
return {};
}

Majority Element
Question

Find element appearing more than n/2 times.

Python
def majority(arr):
return max(set(arr), key=[Link])

Java
static int majority(int[] arr) {
int count = 0, candidate = 0;
for (int num : arr) {
if (count == 0) candidate = num;
count += (num == candidate) ? 1 : -1;
}
return candidate;
}

C++
int majorityElement(vector<int>& arr) {
int count = 0, candidate = 0;
for (int x : arr) {
if (count == 0) candidate = x;

BY: coding_error1
 count += (x == candidate) ? 1 : -1;
}
return candidate;
}

Stock Buy & Sell (One Transaction)

Question

Max profit with one buy and one sell.

Python
def max_profit(prices):
min_price = prices[0]
profit = 0
for p in prices:
profit = max(profit, p - min_price)
min_price = min(min_price, p)
return profit

Java
static int maxProfit(int[] prices) {
int min = prices[0], profit = 0;
for (int p : prices) {
profit = [Link](profit, p - min);
min = [Link](min, p);
}
return profit;
}

C++
int maxProfit(vector<int>& prices) {
int minPrice = prices[0], profit = 0;
for (int p : prices) {
profit = max(profit, p - minPrice);
minPrice = min(minPrice, p);
}
return profit;
}

1 Find Maximum Element in Array

Python

def findMax(arr):
return max(arr)

Java

BY: coding_error1
int findMax(int[] arr){
int max = arr[0];
for(int i=1;i<[Link];i++){
if(arr[i]>max) max=arr[i];
}
return max;
}

C++

int findMax(vector<int>& arr){

int max=arr[0];
for(int i=1;i<[Link]();i++){
if(arr[i]>max) max=arr[i];
}
return max;
}

1 Find Minimum Element in Array

Python

def findMin(arr):
return min(arr)

Java

int findMin(int[] arr){

int min = arr[0];
for(int i=1;i<[Link];i++){
if(arr[i]<min) min=arr[i];
}
return min;
}

C++

int findMin(vector<int>& arr){

int min=arr[0];
for(int i=1;i<[Link]();i++){
if(arr[i]<min) min=arr[i];
}
return min;
}

1 Reverse an Array

Python

def reverseArray(arr):
return arr[::-1]

Java

BY: coding_error1
void reverseArray(int[] arr){
int l=0, r=[Link]-1;
while(l<r){
int temp=arr[l]; arr[l]=arr[r]; arr[r]=temp;
l++; r--;
}
}

C++

void reverseArray(vector<int>& arr){

int l=0,r=[Link]()-1;
while(l<r){
swap(arr[l], arr[r]);
l++; r--;
}
}

1 Check if Array is Sorted

Python

def isSorted(arr):
return all(arr[i]<=arr[i+1] for i in range(len(arr)-1))

Java

boolean isSorted(int[] arr){

for(int i=0;i<[Link]-1;i++){
if(arr[i]>arr[i+1]) return false;
}
return true;
}

C++

bool isSorted(vector<int>& arr){

for(int i=0;i<[Link]()-1;i++){
if(arr[i]>arr[i+1]) return false;
}
return true;
}

1 Check String Rotation

Question: Check if s2 is a rotation of s1.

Python
def is_rotation(s1, s2):
return len(s1) == len(s2) and s2 in s1 + s1

BY: coding_error1
Java
boolean isRotation(String s1, String s2) {
return [Link]() == [Link]() && (s1 + s1).contains(s2);
}

C++
bool isRotation(string s1, string s2) {
return [Link]() == [Link]() && (s1 + s1).find(s2) != string::npos;
}

1 Count Vowels and Consonants

Python
def count_vc(s):
v = sum(1 for c in [Link]() if c in "aeiou")
c = sum(1 for c in [Link]() if [Link]() and c not in "aeiou")
return v, c

Java
int[] countVC(String s) {
int v = 0, c = 0;
for (char ch : [Link]().toCharArray()) {
if ("aeiou".indexOf(ch) != -1) v++;
else if ([Link](ch)) c++;
}
return new int[]{v, c};
}

C++
pair<int,int> countVC(string s) {
int v=0, c=0;
for(char ch: s){
if(isalpha(ch)){
if(string("aeiouAEIOU").find(ch)!=string::npos) v++;
else c++;
}
}
return {v,c};
}

1 Longest Substring Without Repeating Characters

Python
def longest_unique(s):
st, l = set(), 0

BY: coding_error1
 res = 0
for r in range(len(s)):
while s[r] in st:
[Link](s[l]); l += 1
[Link](s[r])
res = max(res, r - l + 1)
return res

Java
int longestUnique(String s) {
Set<Character> set = new HashSet<>();
int l = 0, res = 0;
for (int r = 0; r < [Link](); r++) {
while ([Link]([Link](r)))
[Link]([Link](l++));
[Link]([Link](r));
res = [Link](res, r - l + 1);
}
return res;
}

C++
int longestUnique(string s) {
unordered_set<char> st;
int l=0,res=0;
for(int r=0;r<[Link]();r++){
while([Link](s[r])) [Link](s[l++]);
[Link](s[r]);
res=max(res,r-l+1);
}
return res;
}

1 Valid Parentheses
Python
def is_valid(s):
stack=[]
mp={')':'(',']':'[','}':'{'}
for c in s:
if c in mp:
if not stack or [Link]()!=mp[c]: return False
else: [Link](c)
return not stack

Java
boolean isValid(String s) {
Stack<Character> st = new Stack<>();
for(char c: [Link]()){
if(c=='('||c=='{'||c=='[') [Link](c);
else if([Link]() ||

BY: coding_error1
 (c==')'&&[Link]()!='(') ||
(c=='}'&&[Link]()!='{') ||
(c==']'&&[Link]()!='[')) return false;
}
return [Link]();
}

C++
bool isValid(string s){
stack<char> st;
for(char c:s){
if(c=='('||c=='{'||c=='[') [Link](c);
else{
if([Link]()) return false;
char t=[Link](); [Link]();
if((c==')'&&t!='(')||(c=='}'&&t!='{')||(c==']'&&t!='['))
return false;
}
}
return [Link]();
}

1 Print Numbers Using Recursion

Python
def print_n(n):
if n==0: return
print_n(n-1)
print(n)

Java
void printN(int n){
if(n==0) return;
printN(n-1);
[Link](n+" ");
}

C++
void printN(int n){
if(n==0) return;
printN(n-1);
cout<<n<<" ";
}

2 Factorial
Python

BY: coding_error1
def fact(n):
return 1 if n==0 else n*fact(n-1)

Java
int fact(int n){
return n==0?1:n*fact(n-1);
}

C++
int fact(int n){
return n==0?1:n*fact(n-1);
}

2 Fibonacci (Recursion)
Python
def fib(n):
if n<=1: return n
return fib(n-1)+fib(n-2)

Java
int fib(int n){
if(n<=1) return n;
return fib(n-1)+fib(n-2);
}

C++
int fib(int n){
if(n<=1) return n;
return fib(n-1)+fib(n-2);
}

2 Generate All Subsets

Python
def subsets(nums):
res=[[]]
for n in nums:
res += [x+[n] for x in res]
return res

Java
List<List<Integer>> subsets(int[] nums){

BY: coding_error1
 List<List<Integer>> res=new ArrayList<>();
[Link](new ArrayList<>());
for(int n:nums){
int size=[Link]();
for(int i=0;i<size;i++){
List<Integer> temp=new ArrayList<>([Link](i));
[Link](n);
[Link](temp);
}
}
return res;
}

C++
vector<vector<int>> subsets(vector<int>& nums){
vector<vector<int>> res={{}};
for(int n:nums){
int size=[Link]();
for(int i=0;i<size;i++){
auto temp=res[i];
temp.push_back(n);
res.push_back(temp);
}
}
return res;
}

2 Permutations of String
Python
from itertools import permutations
def permute(s):
return list(permutations(s))

Java
void permute(String s, String ans){
if([Link]()==0){
[Link](ans);
return;
}
for(int i=0;i<[Link]();i++)
permute([Link](0,i)+[Link](i+1), ans+[Link](i));
}

C++
void permute(string s, int l){
if(l==[Link]()-1) cout<<s<<endl;
for(int i=l;i<[Link]();i++){
swap(s[l],s[i]);
permute(s,l+1);
swap(s[l],s[i]);

BY: coding_error1
 }
}

2 N-Queens Problem
Question: Place N queens on an N×N chessboard so that no two queens attack each other.

Python
def solveNQueens(n):
res, board = [], [-1]*n
def dfs(r):
if r == n:
[Link](board[:])
return
for c in range(n):
for i in range(r):
if board[i] == c or abs(board[i]-c) == r-i:
break
else:
board[r] = c
dfs(r+1)
dfs(0)
return res

Java
void solve(int r, int n, int[] board, List<int[]> res){
if(r==n){ [Link]([Link]()); return; }
for(int c=0;c<n;c++){
boolean ok=true;
for(int i=0;i<r;i++)
if(board[i]==c || [Link](board[i]-c)==r-i) ok=false;
if(ok){
board[r]=c;
solve(r+1,n,board,res);
}
}
}

C++
void solve(int r, int n, vector<int>& board, vector<vector<int>>& res){
if(r==n){ res.push_back(board); return; }
for(int c=0;c<n;c++){
bool ok=true;
for(int i=0;i<r;i++)
if(board[i]==c || abs(board[i]-c)==r-i) ok=false;
if(ok){
board[r]=c;
solve(r+1,n,board,res);
}
}
}

BY: coding_error1
2 Rat in a Maze
Python
def ratMaze(m):
n=len(m)
res=[]
def dfs(x,y,path):
if x==n-1 and y==n-1:
[Link](path); return
if x<0 or y<0 or x>=n or y>=n or m[x][y]==0: return
m[x][y]=0
dfs(x+1,y,path+'D')
dfs(x,y+1,path+'R')
dfs(x-1,y,path+'U')
dfs(x,y-1,path+'L')
m[x][y]=1
dfs(0,0,"")
return res

(Java & C++ follow same DFS logic)

2 Reverse a Linked List

Python
def reverse(head):
prev=None
while head:
nxt=[Link]
[Link]=prev
prev=head
head=nxt
return prev

Java
ListNode reverse(ListNode head){
ListNode prev=null;
while(head!=null){
ListNode nxt=[Link];
[Link]=prev;
prev=head;
head=nxt;
}
return prev;
}

C++
ListNode* reverse(ListNode* head){
ListNode* prev=NULL;

BY: coding_error1
 while(head){
ListNode* nxt=head->next;
head->next=prev;
prev=head;
head=nxt;
}
return prev;
}

2 Detect Cycle in Linked List

Python
def hasCycle(head):
slow=fast=head
while fast and [Link]:
slow=[Link]
fast=[Link]
if slow==fast: return True
return False

Java
boolean hasCycle(ListNode head){
ListNode s=head,f=head;
while(f!=null && [Link]!=null){
s=[Link]; f=[Link];
if(s==f) return true;
}
return false;
}

C++
bool hasCycle(ListNode* head){
ListNode *s=head,*f=head;
while(f && f->next){
s=s->next; f=f->next->next;
if(s==f) return true;
}
return false;
}

2 Middle of Linked List

Python
def middle(head):
slow=fast=head
while fast and [Link]:
slow=[Link]
fast=[Link]
return slow

BY: coding_error1
Java
ListNode middle(ListNode head){
ListNode s=head,f=head;
while(f!=null && [Link]!=null){
s=[Link]; f=[Link];
}
return s;
}

C++
ListNode* middle(ListNode* head){
ListNode *s=head,*f=head;
while(f && f->next){
s=s->next; f=f->next->next;
}
return s;
}

2 Merge Two Sorted Linked Lists

Python
def merge(l1,l2):
dummy=cur=ListNode(0)
while l1 and l2:
if [Link]<[Link]:
[Link]=l1; l1=[Link]
else:
[Link]=l2; l2=[Link]
cur=[Link]
[Link]=l1 or l2
return [Link]

(Java & C++ same logic)

3 Remove Nth Node from End

Python
def removeNth(head,n):
dummy=ListNode(0,head)
slow=fast=dummy
for _ in range(n): fast=[Link]
while [Link]:
slow=[Link]; fast=[Link]
[Link]=[Link]
return [Link]

BY: coding_error1
3 Palindrome Linked List
Python
def isPalindrome(head):
vals=[]
while head:
[Link]([Link])
head=[Link]
return vals==vals[::-1]

Java
boolean isPalindrome(ListNode head){
ArrayList<Integer> a=new ArrayList<>();
while(head!=null){ [Link]([Link]); head=[Link]; }
return [Link](new ArrayList<>(a){{
[Link](this);
}});
}

C++
bool isPalindrome(ListNode* head){
vector<int> v;
while(head){ v.push_back(head->val); head=head->next; }
return equal([Link](),[Link](),[Link]());
}

3 Intersection of Two Linked Lists

Python
def getIntersection(a,b):
s=set()
while a: [Link](a); a=[Link]
while b:
if b in s: return b
b=[Link]

3 Add Two Numbers (Linked List)

Python
def addTwo(l1,l2):
carry=0
dummy=cur=ListNode(0)
while l1 or l2 or carry:
s=carry+([Link] if l1 else 0)+([Link] if l2 else 0)
carry=s//10
[Link]=ListNode(s%10)

BY: coding_error1
 cur=[Link]
l1=[Link] if l1 else None
l2=[Link] if l2 else None
return [Link]

3 Stack Using Array

Python
class Stack:
def __init__(self):
self.s=[]
def push(self,x): [Link](x)
def pop(self): return [Link]()

Java
class Stack{
int[] a=new int[100];
int top=-1;
void push(int x){ a[++top]=x; }
int pop(){ return a[top--]; }
}

C++
class Stack{
int a[100], top=-1;
public:
void push(int x){ a[++top]=x; }
int pop(){ return a[top--]; }
};

3 Queue Using Array

Python
class Queue:
def __init__(self):
self.q=[]
def enqueue(self,x): [Link](x)
def dequeue(self): return [Link](0)

Java
class Queue{
int[] a=new int[100];
int f=0,r=0;
void enqueue(int x){ a[r++]=x; }
int dequeue(){ return a[f++]; }
}

BY: coding_error1
C++
class Queue{
int a[100], f=0,r=0;
public:
void enqueue(int x){ a[r++]=x; }
int dequeue(){ return a[f++]; }
};

3 Valid Parentheses
Python
def isValid(s):
stack=[]
mp={')':'(',']':'[','}':'{'}
for c in s:
if c in mp:
if not stack or [Link]()!=mp[c]:
return False
else:
[Link](c)
return not stack

Java
boolean isValid(String s){
Stack<Character> st=new Stack<>();
for(char c:[Link]()){
if(c=='('||c=='{'||c=='[') [Link](c);
else{
if([Link]()) return false;
char t=[Link]();
if((c==')'&&t!='(')||(c=='}'&&t!='{')||(c==']'&&t!='['))
return false;
}
}
return [Link]();
}

C++
bool isValid(string s){
stack<char> st;
for(char c:s){
if(c=='('||c=='{'||c=='[') [Link](c);
else{
if([Link]()) return false;
char t=[Link](); [Link]();
if((c==')'&&t!='(')||(c=='}'&&t!='{')||(c==']'&&t!='['))
return false;
}
}
return [Link]();
}

BY: coding_error1
3 Next Greater Element
Python
def nextGreater(nums):
res=[-1]*len(nums)
st=[]
for i in range(len(nums)):
while st and nums[st[-1]]<nums[i]:
res[[Link]()]=nums[i]
[Link](i)
return res

Java
int[] nextGreater(int[] a){
int n=[Link];
int[] res=new int[n];
[Link](res,-1);
Stack<Integer> st=new Stack<>();
for(int i=0;i<n;i++){
while(![Link]() && a[[Link]()]<a[i])
res[[Link]()]=a[i];
[Link](i);
}
return res;
}

C++
vector<int> nextGreater(vector<int>& a){
int n=[Link]();
vector<int> res(n,-1);
stack<int> st;
for(int i=0;i<n;i++){
while(![Link]() && a[[Link]()]<a[i]){
res[[Link]()]=a[i];
[Link]();
}
[Link](i);
}
return res;
}

3 Stack Using Queue

Python
from collections import deque
class Stack:
def __init__(self):
self.q=deque()
def push(self,x):
[Link](x)

BY: coding_error1
 for _ in range(len(self.q)-1):
[Link]([Link]())
def pop(self):
return [Link]()

Java
class StackUsingQueue{
Queue<Integer> q=new LinkedList<>();
void push(int x){
[Link](x);
for(int i=0;i<[Link]()-1;i++)
[Link]([Link]());
}
int pop(){ return [Link](); }
}

C++
class Stack{
queue<int> q;
public:
void push(int x){
[Link](x);
for(int i=0;i<[Link]()-1;i++){
[Link]([Link]()); [Link]();
}
}
int pop(){ int x=[Link](); [Link](); return x; }
};

3 Queue Using Stack

Python
class Queue:
def __init__(self):
self.s1=[]; self.s2=[]
def enqueue(self,x):
[Link](x)
def dequeue(self):
if not self.s2:
while self.s1:
[Link]([Link]())
return [Link]()

Java
class QueueUsingStack{
Stack<Integer> s1=new Stack<>(), s2=new Stack<>();
void enqueue(int x){ [Link](x); }
int dequeue(){
if([Link]())
while(![Link]()) [Link]([Link]());
return [Link]();

BY: coding_error1
 }
}

C++
class Queue{
stack<int> s1,s2;
public:
void enqueue(int x){ [Link](x); }
int dequeue(){
if([Link]())
while(![Link]()){
[Link]([Link]()); [Link]();
}
int x=[Link](); [Link]();
return x;
}
};

4 Min Stack
Python
class MinStack:
def __init__(self):
self.s=[]; self.m=[]
def push(self,x):
[Link](x)
[Link](x if not self.m else min(x,self.m[-1]))
def pop(self):
[Link](); [Link]()
def getMin(self):
return self.m[-1]

Java
class MinStack{
Stack<Integer> s=new Stack<>(), m=new Stack<>();
void push(int x){
[Link](x);
[Link]([Link]()?x:[Link](x,[Link]()));
}
void pop(){ [Link](); [Link](); }
int getMin(){ return [Link](); }
}

C++
class MinStack{
stack<int> s,m;
public:
void push(int x){
[Link](x);
[Link]([Link]()?x:min(x,[Link]()));
}

BY: coding_error1
 void pop(){ [Link](); [Link](); }
int getMin(){ return [Link](); }
};

4 Frequency of Elements
Python
from collections import Counter
freq = Counter(arr)

Java
HashMap<Integer,Integer> map=new HashMap<>();
for(int x:arr)
[Link](x,[Link](x,0)+1);

C++
unordered_map<int,int> mp;
for(int x:arr) mp[x]++;

4 Two Sum (Hashing)

Python
def twoSum(nums,target):
mp={}
for i,n in enumerate(nums):
if target-n in mp:
return [mp[target-n],i]
mp[n]=i

(Java & C++ similar with HashMap / unordered_map)

4 Longest Consecutive Sequence

Python
def longest(nums):
s=set(nums)
ans=0
for x in s:
if x-1 not in s:
y=x
while y in s: y+=1
ans=max(ans,y-x)
return ans

BY: coding_error1
Java
int longest(int[] a){
Set<Integer> s=new HashSet<>();
for(int x:a) [Link](x);
int ans=0;
for(int x:s)
if(){
int y=x;
while([Link](y)) y++;
ans=[Link](ans,y-x);
}
return ans;
}

C++
int longest(vector<int>& a){
unordered_set<int> s([Link](),[Link]());
int ans=0;
for(int x:s)
if(){
int y=x;
while([Link](y)) y++;
ans=max(ans,y-x);
}
return ans;
}

4 Subarray with Zero Sum

Python
def zeroSum(arr):
s=set(); curr=0
for x in arr:
curr+=x
if curr==0 or curr in s:
return True
[Link](curr)
return False

Java
boolean zeroSum(int[] a){
HashSet<Integer> s=new HashSet<>();
int sum=0;
for(int x:a){
sum+=x;
if(sum==0||[Link](sum)) return true;
[Link](sum);
}
return false;
}

BY: coding_error1
C++
bool zeroSum(vector<int>& a){
unordered_set<int> s;
int sum=0;
for(int x:a){
sum+=x;
if(sum==0||[Link](sum)) return true;
[Link](sum);
}
return false;
}

4 First Non-Repeating Character

Python
from collections import Counter
def firstUnique(s):
c=Counter(s)
for i,ch in enumerate(s):
if c[ch]==1: return i
return -1

Java
int firstUnique(String s){
int[] cnt=new int[26];
for(char c:[Link]()) cnt[c-'a']++;
for(int i=0;i<[Link]();i++)
if(cnt[[Link](i)-'a']==1) return i;
return -1;
}

C++
int firstUnique(string s){
int cnt[26]={0};
for(char c:s) cnt[c-'a']++;
for(int i=0;i<[Link]();i++)
if(cnt[s[i]-'a']==1) return i;
return -1;
}

4 Inorder Traversal (Binary Tree)

Python
def inorder(root):
return inorder([Link])+[[Link]]+inorder([Link]) if root else
[]

BY: coding_error1
Java
void inorder(TreeNode r){
if(r==null) return;
inorder([Link]);
[Link]([Link]+" ");
inorder([Link]);
}

C++
void inorder(Node* r){
if(!r) return;
inorder(r->left);
cout<<r->data<<" ";
inorder(r->right);
}

4 Preorder Traversal
Python
def preorder(root):
return [[Link]]+preorder([Link])+preorder([Link]) if root else
[]

4 Postorder Traversal
Python
def postorder(root):
return postorder([Link])+postorder([Link])+[[Link]] if root
else []

4 Level Order Traversal

Python
from collections import deque
def levelOrder(root):
if not root: return []
q,res=deque([root]),[]
while q:
n=len(q); lvl=[]
for _ in range(n):
r=[Link]()
[Link]([Link])
if [Link]: [Link]([Link])
if [Link]: [Link]([Link])

BY: coding_error1
 [Link](lvl)
return res

5 Height of Binary Tree

Python
def height(root):
if not root: return 0
return 1+max(height([Link]),height([Link]))

Java
int height(TreeNode r){
if(r==null) return 0;
return 1+[Link](height([Link]),height([Link]));
}

C++
int height(Node* r){
if(!r) return 0;
return 1+max(height(r->left),height(r->right));
}

5 Diameter of Binary Tree

Python

def diameter(root):
ans = 0
def dfs(node):
nonlocal ans
if not node: return 0
l = dfs([Link])
r = dfs([Link])
ans = max(ans, l + r)
return 1 + max(l, r)
dfs(root)
return ans

Java

int dia = 0;
int height(TreeNode r){
if(r==null) return 0;
int l = height([Link]);
int h = height([Link]);
dia = [Link](dia, l + h);
return 1 + [Link](l, h);
}

C++

BY: coding_error1
int dia = 0;
int height(Node* r){
if(!r) return 0;
int l = height(r->left);
int h = height(r->right);
dia = max(dia, l + h);
return 1 + max(l, h);
}

5 Check Balanced Binary Tree

Python

def isBalanced(root):
def dfs(n):
if not n: return 0
l = dfs([Link])
r = dfs([Link])
if l == -1 or r == -1 or abs(l-r) > 1: return -1
return 1 + max(l,r)
return dfs(root) != -1

Java

int check(TreeNode r){

if(r==null) return 0;
int l = check([Link]), h = check([Link]);
if(l == -1 || h == -1 || [Link](l-h) > 1) return -1;
return 1 + [Link](l,h);
}

C++

int check(Node* r){

if(!r) return 0;
int l = check(r->left), h = check(r->right);
if(l==-1 || h==-1 || abs(l-h)>1) return -1;
return 1 + max(l,h);
}

5 Lowest Common Ancestor (Binary Tree)

Python

def lca(root, p, q):

if not root or root==p or root==q: return root
l = lca([Link], p, q)
r = lca([Link], p, q)
return root if l and r else l or r

Java

TreeNode lca(TreeNode r, TreeNode p, TreeNode q){

if(r==null||r==p||r==q) return r;

BY: coding_error1
 TreeNode l = lca([Link],p,q);
TreeNode h = lca([Link],p,q);
return (l!=null && h!=null) ? r : (l!=null ? l : h);
}

C++

Node* lca(Node* r, Node* p, Node* q){

if(!r || r==p || r==q) return r;
Node* l = lca(r->left,p,q);
Node* h = lca(r->right,p,q);
return (l && h) ? r : (l ? l : h);
}

5 Maximum Path Sum

Python

def maxPathSum(root):
ans = float('-inf')
def dfs(n):
nonlocal ans
if not n: return 0
l = max(0, dfs([Link]))
r = max(0, dfs([Link]))
ans = max(ans, [Link] + l + r)
return [Link] + max(l,r)
dfs(root)
return ans

Java

int ans = Integer.MIN_VALUE;

int dfs(TreeNode n){
if(n==null) return 0;
int l = [Link](0, dfs([Link]));
int r = [Link](0, dfs([Link]));
ans = [Link](ans, [Link] + l + r);
return [Link] + [Link](l,r);
}

C++

int ans = INT_MIN;

int dfs(Node* n){
if(!n) return 0;
int l = max(0, dfs(n->left));
int r = max(0, dfs(n->right));
ans = max(ans, n->data + l + r);
return n->data + max(l,r);
}

5 Serialize Binary Tree

BY: coding_error1
Python

def serialize(root):
if not root: return "#"
return str([Link]) + "," + serialize([Link]) + "," +
serialize([Link])

Java

String serialize(TreeNode root){

if(root==null) return "#";
return [Link] + "," + serialize([Link]) + "," +
serialize([Link]);
}

C++

string serialize(Node* root){

if(!root) return "#";
return to_string(root->data) + "," + serialize(root->left) + "," +
serialize(root->right);
}

5 Binary Search

Python

def binarySearch(a, x):

l, r = 0, len(a)-1
while l <= r:
m = (l+r)//2
if a[m] == x: return m
elif a[m] < x: l = m + 1
else: r = m - 1
return -1

Java

int binarySearch(int[] a, int x){

int l = 0, r = [Link]-1;
while(l <= r){
int m = (l+r)/2;
if(a[m] == x) return m;
else if(a[m] < x) l = m+1;
else r = m-1;
}
return -1;
}

C++

int binarySearch(vector<int>& a, int x){

int l=0, r=[Link]()-1;
while(l<=r){
int m=(l+r)/2;

BY: coding_error1
 if(a[m]==x) return m;
else if(a[m]<x) l=m+1;
else r=m-1;
}
return -1;
}

5 First & Last Occurrence

Python

import bisect
def firstLast(a, x):
return bisect.bisect_left(a,x), bisect.bisect_right(a,x)-1

Java

int firstOccurrence(int[] a, int x){

int l=0, r=[Link]-1, ans=-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==x){ ans=m; r=m-1; }
else if(a[m]<x) l=m+1;
else r=m-1;
}
return ans;
}
int lastOccurrence(int[] a, int x){
int l=0, r=[Link]-1, ans=-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==x){ ans=m; l=m+1; }
else if(a[m]<x) l=m+1;
else r=m-1;
}
return ans;
}

C++

int firstOccurrence(vector<int>& a, int x){

int l=0,r=[Link]()-1,ans=-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==x){ ans=m; r=m-1; }
else if(a[m]<x) l=m+1;
else r=m-1;
}
return ans;
}
int lastOccurrence(vector<int>& a, int x){
int l=0,r=[Link]()-1,ans=-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]==x){ ans=m; l=m+1; }
else if(a[m]<x) l=m+1;
else r=m-1;

BY: coding_error1
 }
return ans;
}

5 Search in Rotated Sorted Array

Python

def searchRotated(nums, target):

l,r=0,len(nums)-1
while l<=r:
m=(l+r)//2
if nums[m]==target: return m
if nums[l]<=nums[m]:
if nums[l]<=target<nums[m]: r=m-1
else: l=m+1
else:
if nums[m]<target<=nums[r]: l=m+1
else: r=m-1
return -1

5 Square Root of Number

Python

def sqrt(x):
l,r=0,x
ans=0
while l<=r:
m=(l+r)//2
if m*m<=x: ans=m; l=m+1
else: r=m-1
return ans

6 Peak Element

Python

def peak(nums):
l,r=0,len(nums)-1
while l<r:
m=(l+r)//2
if nums[m]<nums[m+1]: l=m+1
else: r=m
return l

Java

int peakElement(int[] nums){

int l=0,r=[Link]-1;
while(l<r){
int m=(l+r)/2;

BY: coding_error1
 if(nums[m]<nums[m+1]) l=m+1;
else r=m;
}
return l;
}

C++

int peakElement(vector<int>& nums){

int l=0,r=[Link]()-1;
while(l<r){
int m=(l+r)/2;
if(nums[m]<nums[m+1]) l=m+1;
else r=m;
}
return l;
}

6 BFS Traversal

Python

from collections import deque

def bfs(graph, start):
vis = set([start])
q = deque([start])
order = []
while q:
u = [Link]()
[Link](u)
for v in graph[u]:
if v not in vis:
[Link](v)
[Link](v)
return order

Java

List<Integer> bfs(Map<Integer, List<Integer>> graph, int start){

Set<Integer> vis = new HashSet<>();
Queue<Integer> q = new LinkedList<>();
List<Integer> order = new ArrayList<>();
[Link](start); [Link](start);
while(![Link]()){
int u = [Link]();
[Link](u);
for(int v : [Link](u)){
if(){
[Link](v);
[Link](v);
}
}
}
return order;
}

C++

BY: coding_error1
vector<int> bfs(unordered_map<int, vector<int>>& graph, int start){
unordered_set<int> vis;
queue<int> q;
vector<int> order;
[Link](start); [Link](start);
while(![Link]()){
int u = [Link](); [Link]();
order.push_back(u);
for(int v : graph[u]){
if(){
[Link](v);
[Link](v);
}
}
}
return order;
}

6 DFS Traversal

Python

def dfs(graph, u, vis=None, order=None):

if vis is None: vis=set()
if order is None: order=[]
[Link](u)
[Link](u)
for v in graph[u]:
if v not in vis:
dfs(graph,v,vis,order)
return order

Java

void dfs(Map<Integer,List<Integer>> graph, int u, Set<Integer> vis,

List<Integer> order){
[Link](u);
[Link](u);
for(int v: [Link](u)){
if() dfs(graph,v,vis,order);
}
}

C++

void dfs(unordered_map<int, vector<int>>& graph, int u, unordered_set<int>&

vis, vector<int>& order){
[Link](u);
order.push_back(u);
for(int v : graph[u]){
if() dfs(graph,v,vis,order);
}
}

6 Cycle Detection (Undirected)

BY: coding_error1
Python

def hasCycle(graph):
vis=set()
def dfs(u,p):
[Link](u)
for v in graph[u]:
if v not in vis:
if dfs(v,u): return True
elif v!=p: return True
return False
for node in graph:
if node not in vis and dfs(node,-1): return True
return False

Java

boolean hasCycle(Map<Integer,List<Integer>> g){

Set<Integer> vis = new HashSet<>();
for(int u : [Link]()){
if( && dfs(u,-1,g,vis)) return true;
}
return false;
}
boolean dfs(int u,int p, Map<Integer,List<Integer>> g, Set<Integer> vis){
[Link](u);
for(int v : [Link](u)){
if(){
if(dfs(v,u,g,vis)) return true;
} else if(v!=p) return true;
}
return false;
}

C++

bool dfs(int u, int p, unordered_map<int,vector<int>>& g,

unordered_set<int>& vis){
[Link](u);
for(int v:g[u]){
if(){
if(dfs(v,u,g,vis)) return true;
} else if(v!=p) return true;
}
return false;
}
bool hasCycle(unordered_map<int,vector<int>>& g){
unordered_set<int> vis;
for(auto &it:g){
if( && dfs([Link],-1,g,vis)) return true;
}
return false;
}

6 Cycle Detection (Directed)

Python

BY: coding_error1
def cycleDir(graph):
vis, rec = set(), set()
def dfs(u):
[Link](u)
[Link](u)
for v in graph[u]:
if v not in vis and dfs(v): return True
if v in rec: return True
[Link](u)
return False
return any(dfs(node) for node in graph if node not in vis)

6 Number of Islands

Python

def numIslands(grid):
m,n=len(grid),len(grid[0])
def dfs(i,j):
if i<0 or j<0 or i>=m or j>=n or grid[i][j]=='0': return
grid[i][j]='0'
for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:
dfs(i+dx,j+dy)
cnt=0
for i in range(m):
for j in range(n):
if grid[i][j]=='1':
cnt+=1
dfs(i,j)
return cnt

Java

int numIslands(char[][] grid){

int m=[Link],n=grid[0].length, count=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1'){ count++; dfs(grid,i,j,m,n); }
}
}
return count;
}
void dfs(char[][] g,int i,int j,int m,int n){
if(i<0||j<0||i>=m||j>=n||g[i][j]=='0') return;
g[i][j]='0';
dfs(g,i+1,j,m,n); dfs(g,i-1,j,m,n);
dfs(g,i,j+1,m,n); dfs(g,i,j-1,m,n);
}

C++

void dfs(vector<vector<char>>& g,int i,int j,int m,int n){

if(i<0||j<0||i>=m||j>=n||g[i][j]=='0') return;
g[i][j]='0';
dfs(g,i+1,j,m,n); dfs(g,i-1,j,m,n);
dfs(g,i,j+1,m,n); dfs(g,i,j-1,m,n);
}

BY: coding_error1
int numIslands(vector<vector<char>>& g){
int m=[Link](), n=g[0].size(), count=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(g[i][j]=='1'){ count++; dfs(g,i,j,m,n); }
}
}
return count;
}

6 Topological Sort (DFS)

Python

def topoSort(graph):
vis = set()
res = []
def dfs(u):
[Link](u)
for v in graph[u]:
if v not in vis: dfs(v)
[Link](u)
for node in graph:
if node not in vis: dfs(node)
return res[::-1]

6 Dijkstra (Shortest Path)

Python

import heapq
def dijkstra(graph, start):
dist = {i:float('inf') for i in graph}
dist[start] = 0
pq = [(0,start)]
while pq:
d,u = [Link](pq)
if d>dist[u]: continue
for v,w in graph[u]:
if dist[u]+w<dist[v]:
dist[v] = dist[u]+w
[Link](pq,(dist[v],v))
return dist

6 Bipartite Graph Check

Python

def bipartite(graph):
color = {}
def dfs(u, c):
color[u] = c
for v in graph[u]:

BY: coding_error1
 if v not in color:
if not dfs(v,1-c): return False
elif color[v]==c: return False
return True
return all(dfs(u,0) for u in graph if u not in color)

6 Fibonacci (DP)

Python

def fib(n):
if n<=1: return n
a,b=0,1
for _ in range(2,n+1):
a,b=b,a+b
return b

Java

int fib(int n){

if(n<=1) return n;
int a=0,b=1;
for(int i=2;i<=n;i++){
int c=a+b; a=b; b=c;
}
return b;
}

C++

int fib(int n){

if(n<=1) return n;
int a=0,b=1;
for(int i=2;i<=n;i++){
int c=a+b; a=b; b=c;
}
return b;
}

7 Climbing Stairs

Python

def climb(n):
a,b=1,1
for _ in range(n-1):
a,b=b,a+b
return b

Java

int climbStairs(int n){

int a=1,b=1;
for(int i=1;i<n;i++){

BY: coding_error1
 int t=a+b; a=b; b=t;
}
return b;
}

C++

int climbStairs(int n){

int a=1,b=1;
for(int i=1;i<n;i++){
int t=a+b; a=b; b=t;
}
return b;
}

7 Coin Change (Minimum Coins)

Python

def coinChange(coins, amount):

dp = [float('inf')] * (amount+1)
dp[0] = 0
for i in range(1, amount+1):
for c in coins:
if i>=c:
dp[i] = min(dp[i], dp[i-c]+1)
return dp[amount] if dp[amount]!=float('inf') else -1

Java

int coinChange(int[] coins, int amount){

int[] dp = new int[amount+1];
[Link](dp,Integer.MAX_VALUE);
dp[0]=0;
for(int i=1;i<=amount;i++){
for(int c: coins){
if(i>=c && dp[i-c]!=Integer.MAX_VALUE)
dp[i] = [Link](dp[i], dp[i-c]+1);
}
}
return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
}

C++

int coinChange(vector<int>& coins, int amount){

vector<int> dp(amount+1, INT_MAX);
dp[0]=0;
for(int i=1;i<=amount;i++){
for(int c: coins){
if(i>=c && dp[i-c]!=INT_MAX) dp[i]=min(dp[i], dp[i-c]+1);
}
}
return dp[amount]==INT_MAX?-1:dp[amount];
}

BY: coding_error1
7 Longest Common Subsequence (LCS)

Python

def lcs(a,b):
m,n=len(a),len(b)
dp=[[0]*(n+1) for _ in range(m+1)]
for i in range(1,m+1):
for j in range(1,n+1):
if a[i-1]==b[j-1]: dp[i][j]=1+dp[i-1][j-1]
else: dp[i][j]=max(dp[i-1][j],dp[i][j-1])
return dp[m][n]

Java

int lcs(String a, String b){

int m=[Link](), n=[Link]();
int[][] dp = new int[m+1][n+1];
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if([Link](i-1)==[Link](j-1)) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=[Link](dp[i-1][j],dp[i][j-1]);
}
}
return dp[m][n];
}

C++

int lcs(string a, string b){

int m=[Link](), n=[Link]();
vector<vector<int>> dp(m+1, vector<int>(n+1,0));
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
if(a[i-1]==b[j-1]) dp[i][j]=1+dp[i-1][j-1];
else dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
}
}
return dp[m][n];
}

7 Longest Increasing Subsequence (LIS)

Python

def lis(arr):
n=len(arr)
dp=[1]*n
for i in range(n):
for j in range(i):
if arr[i]>arr[j]:
dp[i]=max(dp[i], dp[j]+1)
return max(dp)

Java

BY: coding_error1
int lis(int[] arr){
int n=[Link];
int[] dp=new int[n];
[Link](dp,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(arr[i]>arr[j]) dp[i]=[Link](dp[i], dp[j]+1);
}
}
int max=0;
for(int x: dp) max=[Link](max,x);
return max;
}

C++

int lis(vector<int>& arr){

int n=[Link]();
vector<int> dp(n,1);
for(int i=0;i<n;i++){
for(int j=0;j<i;j++){
if(arr[i]>arr[j]) dp[i]=max(dp[i], dp[j]+1);
}
}
return *max_element([Link](), [Link]());
}

7 0/1 Knapsack Problem

Python

def knapsack(wt, val, W):

n=len(wt)
dp=[[0]*(W+1) for _ in range(n+1)]
for i in range(1,n+1):
for j in range(W+1):
if wt[i-1]<=j:
dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]], dp[i-1][j])
else:
dp[i][j]=dp[i-1][j]
return dp[n][W]

Java

int knapsack(int[] wt,int[] val,int W){

int n=[Link];
int[][] dp=new int[n+1][W+1];
for(int i=1;i<=n;i++){
for(int j=0;j<=W;j++){
if(wt[i-1]<=j)
dp[i][j]=[Link](val[i-1]+dp[i-1][j-wt[i-1]], dp[i-1][j]);
else dp[i][j]=dp[i-1][j];
}
}
return dp[n][W];
}

BY: coding_error1
C++

int knapsack(vector<int>& wt, vector<int>& val, int W){

int n=[Link]();
vector<vector<int>> dp(n+1, vector<int>(W+1,0));
for(int i=1;i<=n;i++){
for(int j=0;j<=W;j++){
if(wt[i-1]<=j)
dp[i][j]=max(val[i-1]+dp[i-1][j-wt[i-1]], dp[i-1][j]);
else dp[i][j]=dp[i-1][j];
}
}
return dp[n][W];
}

7 Matrix Chain Multiplication

Python

def matrixChain(arr):
n=len(arr)
dp=[[0]*n for _ in range(n)]
for l in range(2,n):
for i in range(1,n-l+1):
j=i+l-1
dp[i][j]=float('inf')
for k in range(i,j):
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+arr[i-
1]*arr[k]*arr[j])
return dp[1][n-1]

Java

int matrixChain(int[] arr){

int n=[Link];
int[][] dp=new int[n][n];
for(int l=2;l<n;l++){
for(int i=1;i<n-l+1;i++){
int j=i+l-1;
dp[i][j]=Integer.MAX_VALUE;
for(int k=i;k<j;k++){
dp[i][j]=[Link](dp[i][j], dp[i][k]+dp[k+1][j]+arr[i-
1]*arr[k]*arr[j]);
}
}
}
return dp[1][n-1];
}

C++

int matrixChain(vector<int>& arr){

int n=[Link]();
vector<vector<int>> dp(n, vector<int>(n,0));
for(int l=2;l<n;l++){
for(int i=1;i<n-l+1;i++){
int j=i+l-1;

BY: coding_error1
 dp[i][j]=INT_MAX;
for(int k=i;k<j;k++)
dp[i][j]=min(dp[i][j], dp[i][k]+dp[k+1][j]+arr[i-
1]*arr[k]*arr[j]);
}
}
return dp[1][n-1];
}

___________________________________________________________________________

Best of Luck!

Prepare these DSA questions well, master the concepts, and confidently apply for your dream
job. Every effort you put in now will pay off in your career journey!

BY: @coding_error1

BY: coding_error1