SDOT

MERGE TWO SORTED LINKED

LISTS
Merge Two Sorted Linked Lists
Merge two sorted linked lists and return it as a sorted list. The
list should be made by splicing together the nodes of the first two
lists.
Input Format
The format for each test case is as follows:

The first line contains an integer n, the length of the first linked
list.
The next line contain n integers, the elements of the linked list.
The next line contains an integer m , the length of the second linked
list.
The next lines contain m integers, the elements of the second linked
list.

Output Format
Example

Input
3
1 2 4
3
1 3 4
Output

1 1 2 3 4 4
LOGIC: Input:
Array 1: 1 2 4
Array 2: 1 3 4
Output:
Merged Array: 1 1 2 3 4 4
Logic:
1. Start with two sorted arrays.
2. Initialize pointers for each array, starting at the first element
Pointer for Array 1: 1
Pointer for Array 2: 1
3. Compare the elements at the pointers. Choose the smaller element and
append it to the merged array.
Merged Array: 1
Increment pointers for both arrays.
4. Repeat the comparison and appending process until one of the arrays is
exhausted
Merged Array: 1 1 2 3
5. Once one array is exhausted, append the remaining elements from the
other array to the merged array.
Merged Array: 1 1 2 3 4 4
PYTHON CODE
class ListNode: else:
def __init__(self, value=0, [Link] = l2
next=None): l2 = [Link]
[Link] = value current = [Link]
[Link] = next
# If any list is not exhausted,
def merge_sorted_lists(l1, l2): append the remaining nodes
# Dummy node to start the merged list if l1 is not None:
dummy = ListNode() [Link] = l1
current = dummy elif l2 is not None:
[Link] = l2
# Traverse both lists until one of
them is exhausted # Return the merged list starting
while l1 is not None and l2 is not from the dummy node's next
None: return [Link]
if [Link] < [Link]:
[Link] = l1 # Helper function to create a linked list
l1 = [Link] from a list of values
def create_linked_list(values):
if not values: # Sample sorted values for the first and
return None second lists
head = ListNode(values[0]) list1_values = [1, 3, 15, 67]
current = head list2_values = [2, 4, 6]
for value in values[1:]:
[Link] = ListNode(value) # Create two sorted linked lists
current = [Link] list1 = create_linked_list(list1_values)
return head list2 = create_linked_list(list2_values)

# Helper function to print the linked # Merge the two lists

list merged_list = merge_sorted_lists(list1,
def print_linked_list(head): list2)
while head is not None:
print([Link], end=" ") # Print the merged list
head = [Link] print("Merged List:")
print() print_linked_list(merged_list)
JAVA CODE
import [Link].*; Node current = head;
import [Link].*; while([Link] !=null){
class Node{ current = [Link];
int data; }
Node next; [Link] = new_node;
Node(int data){ }
[Link] = data; }
next = null; class Solution {
} static Node merge(Node head1, Node
} head2){
class LinkedList{ // Write your code here
Node head; if(head1==null)
void add(int data ){ {
Node new_node = new return head2;
Node(data); }
if(head == null){ if(head2==null)
head = new_node; {
return; return head1;
} }
Node ansHead; //NEW HEAD else{
if([Link]<[Link]){ [Link]=head2;
ansHead=head1; head2=[Link];
head1=[Link]; }
} temp=[Link];
else{ }
ansHead=head2; if(head1!=null){
head2=[Link]; [Link]=head1;
} }
Node temp=ansHead; // if(head2!=null){
after doing all temp will be at [Link]=head2;
last position }
while(head1!=null && head2! return ansHead;
=null){
}
if([Link]<[Link]){ }
public class Main {
[Link]=head1; // ansHead is public static void main(String
already decided so we will traverse args[]) {
from //[Link]
 Scanner sc = new Solution Ob = new Solution();
Scanner([Link]); Node head =
int n = [Link](); [Link]([Link], [Link]);
LinkedList l1= new while(head != null){
LinkedList();
for(int i=0;i<n;i++){ [Link]([Link] + " ");
[Link]([Link]()); head = [Link];
} }
int m = [Link](); }
LinkedList l2 = new }
LinkedList();
for(int i=0;i<m;i++){
[Link]([Link]());
}
PALINDROME LIST
Given a singly linked list of characters, write a function that
returns true if the given list is a palindrome, else false.

Input Format
You will be provided with the linked list''s head.

Output Format
Return true if the given list is a palindrome, else false..
Example 1
Input
5
1 2 3 2 1
Output
true
Example 2
Input
6
10 20 30 10 50 30
Output:
false
LOGIC
Example

Input
3
1 2 4
3
1 3 4
Output

1 1 2 3 4 4
PYTHON CODE
class ListNode: # Function to check if two lists
def __init__(self, value=0, are equal
next=None): def are_lists_equal(list1,
[Link] = value list2):
[Link] = next while list1 and list2:
if [Link] !=
def is_palindrome(head): [Link]:
# Function to reverse a linked return False
list list1 = [Link]
def reverse_list(node): list2 = [Link]
prev = None return True
while node:
next_node = [Link] # Find the middle of the linked
[Link] = prev list
prev = node slow = fast = head
node = next_node while fast and [Link]:
return prev slow = [Link]
fast = [Link]
# Reverse the second half of the
linked list # Create a linked list
reversed_second_half = head = None
reverse_list(slow) for value in reversed(values):
head = ListNode(value, head)
# Compare the first half with
the reversed second half # Check if the linked list is a
return are_lists_equal(head, palindrome
reversed_second_half) result = is_palindrome(head)

# Example usage: # Print the result

# Get input from the user print(result)
n = int(input("Enter the number of
elements in the linked list: "))
values = list(map(int, input("Enter
the elements of the linked list:
").split()))
JAVA CODE
import [Link]; slow = [Link];
class ListNode { fast = [Link];
char val; }
ListNode next; ListNode secondHalf =
public ListNode(char val) { reverseList(slow);
[Link] = val; while (secondHalf != null)
} {
} if ([Link] !=
public class PalindromeList { [Link]) {
public static boolean return false; //
isPalindrome(ListNode head) { The list is not a palindrome
if (head == null || }
[Link] == null) { head = [Link];
return true; secondHalf =
} [Link];
ListNode slow = head, fast }
= head; return true; // The list is
while (fast != null && a palindrome
[Link] != null) { }
 private static ListNode [Link]("Enter the number of
reverseList(ListNode head) { elements in the linked list:");
ListNode prev = null; int n = [Link]();
ListNode current = head; [Link]("Enter the
ListNode next; elements of the linked list:");
while (current != null) { ListNode list = new
next = [Link]; ListNode([Link]().charAt(0));
[Link] = prev; ListNode current = list;
prev = current; for (int i = 1; i < n; i++) {
current = next; [Link] = new
} ListNode([Link]().charAt(0));
return prev; current = [Link];
} }
public static void main(String[] [Link]("Is the linked
args) { list a palindrome? " +
Scanner scanner = new isPalindrome(list));
Scanner([Link]); [Link]();
}
}
MERGE K SORTED LINKED
LISTS
You are given an array of k linkedlists, where each linked list is sorted in ascending
order. Write a Java program to merge all the linked lists into a single linked list and
return it.
Input:
An integer `k` representing the number of linkedlists.
For each linkedlist:
An integer `size` representing the number of elements in the linkedlist.
`size` integers representing the elements of the linkedlist in sorted order.
Output:
A single line containing the elements of the merged linked list in sorted order.
Example 1:
Input:
Enter the number of linkedlists (k):
2
Enter the size of linkedlist 1:
4
Enter the elements of linkedlist 1:
1 4 5 6
Enter the size of linkedlist 2:
3
Enter the elements of linkedlist 2:
1 2 4 5
Output:
Merged Linked List:
1 1 2 4 4 5 6
Example 2:
Input:
Enter the number of linkedlists (k):
3
Enter the size of linkedlist 1:
3
Enter the elements of linkedlist 1:
1 3 7
Enter the size of linkedlist 2:
2
Enter the elements of linkedlist 2:
2 4
Enter the size of linkedlist 3:
4
Enter the elements of linkedlist 3:
5 6 8 9
Output:
Merged Linked List:
1 2 3 4 5 6 7 8 9
LOGIC
⮚ Create a priority queue (min-heap) to keep track of the smallest element from each
linked list.
⮚ Insert the first element from each linked list into the priority queue along with the
index of the linked list.
⮚ Pop the smallest element from the priority queue.
⮚ Append the popped element to the merged linked list.
⮚ If there is a next element in the linked list from which the element was popped,
insert that next element into the priority queue.
⮚ Repeat steps 3-5 until the priority queue is empty.
⮚ The merged linked list is now sorted.
PYTHON CODE
class ListNode: # Continue until the heap is not empty
def __init__(self, value=0, while heap:
next=None): _, min_node = heappop(heap)
[Link] = value [Link] = min_node
[Link] = next current = [Link]

def merge_k_sorted_lists(lists): # Add the next node of the

from heapq import heapify, heappush, min_node to the heap
heappop if min_node.next:
heappush(heap,
# Create a min heap and heapify it (min_node.[Link], min_node.next))
with tuples (value, node)
heap = [([Link], node) for node # Return the merged list starting
in lists if node] from the dummy node's next
heapify(heap) return [Link]
# Dummy node to start the merged list
dummy = ListNode() # Helper function to create a linked list
current = dummy from a list of values
def create_linked_list(values):
if not values: for i in range(k):
return None elements = list(map(int,
head = ListNode(values[0]) input(f"Enter the elements of
current = head linked list {i+1}: ").split()))
for value in values[1:]:
[Link] = [Link](create_linked_list(ele
ListNode(value) ments))
current = [Link]
return head # Merge the k sorted lists
# Helper function to print the merged_list =
linked list merge_k_sorted_lists(lists)
def print_linked_list(head):
while head is not None: # Print the merged list
print([Link], end=" ") print("\nMerged Linked List:")
head = [Link] print_linked_list(merged_list)
print()
# Get input from the user
k = int(input("Enter the number of
linked lists (k): "))
lists = []
JAVA CODE
import [Link]; PriorityQueue<ListNode> minHeap = new
import [Link]; PriorityQueue<>((a, b) -> [Link] - [Link]);
import [Link]; for (ListNode list : lists) {
import [Link]; if (list != null) {
class ListNode { [Link](list);
int val; }
ListNode next; }
ListNode dummy = new ListNode(0);
public ListNode(int val) { ListNode current = dummy;
[Link] = val; while (![Link]()) {
} ListNode minNode =
} [Link]();
public class MergeKSortedArrays { [Link] = minNode;
public static ListNode current = [Link];
mergeKLists(List<ListNode> lists) {
if (lists == null || if ([Link] != null) {
[Link]()) {
return null;
}
[Link]([Link]); [Link]("Enter the number of
} linked-lists (k):");
} int k = [Link]();
return [Link]; List<ListNode> lists = new
} ArrayList<>();
private static void for (int i = 0; i < k; i++) {
printLinkedList(ListNode head) { [Link]("Enter the
while (head != null) { size of linked-list " + (i + 1) + ":");
[Link]([Link] + " int size = [Link]();
"); [Link]("Enter the
head = [Link]; elements of linked-list " + (i + 1) +
} ":");
[Link](); ListNode head = new
} ListNode([Link]());
public static void main(String[] ListNode current = head;
args) {
Scanner scanner = new
Scanner([Link]);
for (int j = 1; j < size; j++) {
[Link] = new
ListNode([Link]());
current = [Link];
}
[Link](head);
}
ListNode mergedList = mergeKLists(lists);
[Link]("Merged Linked List:");
printLinkedList(mergedList);
[Link]();
}
}
REVERSE K ELEMENTS
Reversing a Linked List Given a linked list and a positive number k,

reverse the nodes in groups of k. All the remaining nodes after

multiples of k should be left as it is.

Example 1:

Input:

Linked list: 1→2→3→4→5→6→7→8→9

k: 3

Output:

Result: 3→2→1→6→5→4→9→8→7
Example 2:

Input:

Linked list: 1→2→3→4→5→6→7

k: 2

Output:

Result: 2→1→4→3→6→5→7
LOGIC

Traverse the linked list

and split in groups of k

nodes.

Reverse each group of k

nodes.

Connect the reversed

groups.
PYTHON CODE
class ListNode: # Initialize pointers
def __init__(self, value=0, dummy = ListNode()
next=None): [Link] = head
[Link] = value current = dummy
[Link] = next
# Reverse nodes in groups of k
def reverse_k_elements(head, k): while [Link] is not None:
def reverse_group(curr, k): prev, start, end =
prev, temp = None, curr reverse_group([Link], k)
count = 0 [Link] = prev
[Link] = end
# Count the number of nodes in current = start
the group
while temp is not None and count return [Link]
< k:
next_node = [Link] # Helper function to create a linked list
[Link] = prev from a list of values
prev = temp def create_linked_list(values):
temp = next_node if not values:
count += 1 return None
head = ListNode(values[0])
return prev, curr, temp current = head
for value in values[1:]: # Create a linked list
[Link] = ListNode(value) head = create_linked_list(elements)
current = [Link]
return head # Reverse nodes in groups of k
result = reverse_k_elements(head, k)
# Helper function to print the linked
list # Print the result
def print_linked_list(head): print("\nResult:")
while head is not None: print_linked_list(result)
print([Link], end=" ")
head = [Link]
print()

# Get input from the user

elements = list(map(int, input("Enter the
elements of the linked list: ").split()))
k = int(input("Enter the value of k: "))
JAVA CODE
import [Link]; count++;
class ListNode { }
int val; if (next != null) {
ListNode next; [Link] = reverse(next,
ListNode(int val) { k);
[Link] = val; }
} return prev;
} }
public class ReverseInGroups { private static void
private static ListNode printList(ListNode head) {
reverse(ListNode head, int k) { while (head != null) {
ListNode prev = null; [Link]([Link]
ListNode current = head; + "→");
ListNode next = null; head = [Link];
int count = 0; }
while (count < k && current != [Link]("null");
null) { }
next = [Link]; public static void main(String[]
[Link] = prev; args) {
prev = current; Scanner scanner = new
current = next; Scanner([Link]);
 [Link]("Enter the linked list values (separated
by space):");
String[] values = [Link]().split(" ");
ListNode head = new
ListNode([Link](values[0]));
ListNode current = head;
for (int i = 1; i < [Link]; i++) {
[Link] = new
ListNode([Link](values[i]));
current = [Link];
}
[Link]("Enter the value of k:");
int k = [Link]();
head = reverse(head, k);
[Link]("Result:");
printList(head);
[Link]();
}
}
REORDER LIST
You are given the head of a singly linked list.
The list can be represented as :
L0 → L1 → … → Ln - 1 → Ln
Reorder the list to be on the following form:
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
Examples:

Example 1:

Input: N = 5, List = {1, 2, 3, 4,

5}
 Inpu
t

Output:
Example 2:

Input: N = 4, List = {1, 2, 3, 4}

Output:
PYTHON CODE
class ListNode: list1, list2 = temp1, temp2
def __init__(self, value=0,
next=None): if not head or not [Link]:
[Link] = value return head
[Link] = next slow = fast = head
def reorder_linked_list(head): while [Link] and
def reverse_list(node): [Link]:
prev, current = None, node slow = [Link]
while current: fast = [Link]
next_node = reversed_second_half =
[Link] reverse_list([Link])
[Link] = prev [Link] = None
prev = current merge_lists(head,
current = next_node reversed_second_half)
return prev return head
def merge_lists(list1, list2): def create_linked_list(values):
while list2: if not values:
temp1, temp2 = return None
[Link], [Link] head = ListNode(values[0])
[Link], [Link] current = head
= list2, temp1
 for value in values[1:]: # Create a linked list
[Link] = linked_list =
ListNode(value) create_linked_list(elements)
current = [Link]
return head # Reorder the linked list
reorder_linked_list(linked_list)
def print_linked_list(head):
while head: # Print the result
print([Link], end=" → print("\nReordered Linked List:")
") print_linked_list(linked_list)
head = [Link]
print("None")

# Get input from the user for

linked list values
elements = list(map(int,
input("Enter the elements of the
linked list (space-separated):
").split()))
JAVA CODE
import [Link]; ListNode reverse(ListNode head) {
class ListNode { ListNode curr = head;
int val; ListNode prev = null;
ListNode next; ListNode forw = null;
while (curr != null) {
ListNode(int val) { forw = [Link];
[Link] = val; [Link] = prev;
} prev = curr;
} curr = forw;
class Solution { }
ListNode middle(ListNode head) { return prev;
ListNode slow = head; }
ListNode fast = head; public void reorderList(ListNode
while ([Link] != null && head) {
[Link] != null) { if (head == null || [Link]
slow = [Link]; == null)
fast = [Link]; return;
} ListNode mid = middle(head);
return slow; ListNode k =
} reverse([Link]);
[Link] = null; Scanner scanner = new
ListNode c1 = head; Scanner([Link]);
ListNode c2 = k; [Link]("Enter the
ListNode f1 = null; linked list values (separated by
ListNode f2 = null; space):");
while (c1 != null && c2 != String[] values =
null) { [Link]().split(" ");
f1 = [Link]; ListNode head = new
f2 = [Link]; ListNode([Link](values[0]));
[Link] = c2; ListNode current = head;
[Link] = f1; for (int i = 1; i <
c1 = f1; [Link]; i++) {
c2 = f2; [Link] = new
} ListNode([Link](values[i]));
} current = [Link];
} }
public class Main { Solution solution = new
public static void main(String[] Solution();
args) {
[Link](head);
[Link]("Result:");
printList(head);
[Link]();
}
private static void printList(ListNode head) {
while (head != null) {
[Link]([Link] + "→");
head = [Link];
}
[Link]("null");
}
}
ROTATE LIST
You are given the head of a singly linked list and an integer K, write

a program to Rotate the Linked List in a clockwise direction

by K positions from the last node.

Example

Input-1

Head: 10->20->30->40->50

K: 2

Output-1

40->50->10->20->30
we have rotated the linked list exactly 2 times. On the First rotation 5

becomes head and 4 becomes tail, and on the second rotation 4 becomes head

and 3 becomes the tail node.

LOGIC

• Find the length of the linked list to determine the effective

rotation (adjust k if it's greater than the length).
• Iterate k times, each time moving the last node to the front of
the list.
• Return the updated head of the linked list after rotations.
PYTHON CODE
class ListNode: k = k % length # Adjust k if it's
def __init__(self, value=0, greater than the length of the list
next=None):
[Link] = value for _ in range(k):
[Link] = next temp = head
def insert_node(head, val): while [Link] is not None:
new_node = ListNode(val) temp = [Link]
if head is None: end = [Link]
return new_node [Link] = None
temp = head [Link] = head
while [Link] is not None: head = end
temp = [Link]
[Link] = new_node return head
return head
def rotate_right(head, k): def print_list(head):
if head is None or [Link] is None: while [Link] is not None:
return head print([Link], end="->")
length = 0 head = [Link]
temp = head print([Link])
while temp is not None:
length += 1
temp = [Link]
# Get input from the user
head = None
print("Enter the linked list values (enter -1 to stop):")
while True:
val = int(input())
if val == -1:
break
head = insert_node(head, val)

print("Original list:", end=" ")

print_list(head)

# Get the value of k

k = int(input("Enter the value of k:"))

# Rotate the linked list

new_head = rotate_right(head, k)

print(f"After {k} rotations:", end=" ")

print_list(new_head)
JAVA CODE
import [Link]; Node temp = head;
while ([Link] != null) temp
class Node { = [Link];
int num; [Link] = newNode;
Node next; return head;
}
Node(int a) { static Node rotateRight(Node head,
num = a; int k) {
next = null; if (head == null || [Link]
} == null) return head;
} for (int i = 0; i < k; i++) {
Node temp = head;
public class Main { while ([Link] !=
static Node insertNode(Node head, null) temp = [Link];
int val) { Node end = [Link];
Node newNode = new Node(val); [Link] = null;
if (head == null) { [Link] = head;
head = newNode; head = end;
return head; }
} return head;
}
 static void printList(Node head) { head = insertNode(head, val);
while ([Link] != null) { }
[Link]([Link] [Link]("Original
+ "->"); list: ");
head = [Link]; printList(head);
} [Link]("Enter the
[Link]([Link]); value of k:");
} int k = [Link]();
Node newHead =
public static void main(String rotateRight(head, k);
args[]) { [Link]("After " + k
Scanner scanner = new + " rotations: ");
Scanner([Link]); printList(newHead); // list
Node head = null; after rotating nodes
[Link]("Enter the [Link]();
linked list values (enter -1 to }
stop):"); }
int val;
while ((val =
[Link]()) != -1) {
ODD EVEN LINKED LIST
Given a linked list containing integer values, segregate the even and odd

numbers while maintaining their original order. The even numbers should be

placed at the beginning of the linked list, followed by the odd numbers.
Example 1:

1,2,3
• In our original linked list, we have numbers: 1 → 2 → 3.

• We want to separate even numbers from odd numbers and keep the order

the same.

• So, first, we find the even number, which is 2. We keep it at the

beginning.

• Next, we find the odd numbers, which are 1 and 3. We keep their order

and put them after 2.

• Now, our new linked list is segregated: 2 → 1 → 3.

Example 2:

2 → 1 → 6 → 4 → 8.

Input linked list

2 1 6 4 8

Output linked list

2 4 6 8 1
Example 2:

2 → 1 → 6 → 4 → 8.

In our original linked list, we have numbers: 2 → 1 → 6 → 4 → 8.

We want to separate even numbers from odd numbers and keep the order the same.

So, first, we find the even numbers, which are 2, 6, 4, and 8. We keep them at

the beginning in the same order, forming 2 → 6 → 4 → 8.

Next, we find the odd number, which is 1. We keep it after the even numbers,

maintaining its original order, forming 2 → 6 → 4 → 8 → 1.

Finally, our segregated linked list is: 2 → 6 → 4 → 8 → 1.

Input:

Original list:

1 2 3 4 5

Output:

Segregated list (even before odd):

2 4 1 3 5
 LOGIC
Edge Cases:

If the linked list is empty or has only one node, no rearrangement is needed.

Initialization:

Create two pointers, odd and even, to track the odd and even nodes separately.

Initialize odd to the head of the linked list.

Initialize even to the second node (if exists) or None if there is no second node.

Rearrangement:

Traverse the linked list using a loop until either odd or even becomes None.

Inside the loop, perform the following steps:

Connect the odd node to the next odd node (if exists).

Connect the even node to the next even node (if exists).

Move odd and even pointers to their respective next odd and even nodes.

Continue this process until the end of the linked list is reached.

Finalization:

Connect the last odd node to the starting node of the even nodes.
PYTHON CODE
class ListNode: def create_linked_list(values):
def __init__(self, val=0, next=None): if not values:
[Link] = val return None
[Link] = next head = ListNode(values[0])
def oddEvenList(head): current = head
if not head or not [Link]: for value in values[1:]:
return head [Link] = ListNode(value)
# Separate odd and even nodes current = [Link]
odd_head = odd = ListNode(0) return head
even_head = even = ListNode(0) # Helper function to print the linked list
is_odd = True def print_linked_list(head):
while head: while head:
if is_odd: print([Link], end=" ")
[Link] = head head = [Link]
odd = [Link] print()
else: # Get input from the user
[Link] = head elements = list(map(int, input("Enter the
even = [Link] elements of the linked list: ").split()))
is_odd = not is_odd head = create_linked_list(elements)
head = [Link] # Perform the operation
# Append even nodes to the end of odd nodes result = oddEvenList(head)
[Link] = even_head.next # Print the result
[Link] = None print("\nResulting Linked List:")
return odd_head.next print_linked_list(result)
# Helper function to create a linked list from a
list of values
JAVA CODE
class Node { }
int data; [Link] = newNode;
Node next; }
public Node(int data) { public void segregateEvenOdd() {
[Link] = data; if (head == null) {
[Link] = null; [Link]("The
} list is empty.");
} return;
class LinkedList { }
Node head; Node evenHead = null, evenTail
= null;
public void append(int data) { Node oddHead = null, oddTail =
Node newNode = new Node(data); null;
if (head == null) { Node current = head;
head = newNode; while (current != null) {
return; int data = [Link];
} if (data % 2 == 0) { // even
Node current = head; node
while ([Link] != null) { if (evenHead == null) {
current = [Link]; evenHead = evenTail =
current;
 } else { if (oddHead != null) {
[Link] = current; [Link] = null;
evenTail = current; }
} head = evenHead != null ? evenHead
} else { // odd node : oddHead;
if (oddHead == null) { }
oddHead = oddTail = current;
} else { public void printList() {
[Link] = Node current = head;
current; while (current != null) {
oddTail = current;
} [Link]([Link] + " ");
} current = [Link];
current = [Link]; }
} [Link]();
// Join even and odd lists }
if (evenHead != null) { }
[Link] = oddHead;
}
public class Main {
public static void main(String[] args) {
LinkedList list = new LinkedList();
[Link](1);
[Link](2);
[Link](3);
[Link](4);
[Link](5);

[Link]("Original list:");
[Link]();

[Link]();

[Link]("Segregated list (even before odd):");

[Link]();
}
}
LONGEST VALID PARENTHESES
Given a string containing just the characters '(' and ')', find the length of the longest valid

(well-formed) parentheses substring. A valid parentheses substring is defined as a substring

that has an equal number of '(' and ')' characters and is correctly closed.
Examples:

Input: "(()"

Output: 2

Explanation: The longest valid parentheses substring is "()".

Input: ")()())"

Output: 4

Explanation: The longest valid parentheses substring is "()()".

LOGIC

1. Use a stack to keep track of the indices of opening parentheses.

2. Initialize the stack with 1.

3. Iterate through the string:

For each opening parenthesis '(', push its index onto the stack.

For each closing parenthesis ')', pop from the stack:

If the stack becomes empty, push the current index onto the stack.

If not empty, update the maximum length by calculating the difference between the current

index and the index at the top of the stack.

4. The maximum length is the length of the longest valid parentheses substring.
PYTHON CODE
def longest_valid_parentheses(s):
stack = [-1]
max_length = 0

for i in range(len(s)):
if s[i] == '(':
[Link](i)
else:
[Link]()
if not stack:
[Link](i)
else:
max_length = max(max_length, i - stack[-1])

return max_length

# Example usage
s = "(())"
result = longest_valid_parentheses(s)
print("Length of the longest valid parentheses substring:", result)
JAVA CODE
import [Link];
class Main {
public static void main(String[] args) {
String s = "(()";
Stack<Integer> st = new Stack<>();
int max = 0;
[Link](-1);
for (int i = 0; i < [Link](); i++) {
char c = [Link](i);
if (c == '(') {
[Link](i);
} else {
[Link]();
if ([Link]()) {
[Link](i);
} else {
int len = i - [Link]();
max = [Link](max, len);
}
}
}
[Link]("Length of the longest valid parentheses substring: " +
max);
}
INFIX TO POSTFIX CONVERSION
Implement a Java program that converts an infix expression to a postfix expression using a

stack.

Examples:

Convert the infix expression "(a+b)*(c-d)" to postfix:

Infix: (a+b)*(c-d)

Postfix: ab+cd-*

Convert the infix expression "a+b*c-d/e" to postfix:

Infix: a+b*c-d/e

Postfix: abc*+de/-
LOGIC
✔ Initialize an empty stack for operators and an empty list for the postfix expression.
✔ Scan the infix expression from left to right.
✔ If a character is an operand (letter or digit), add it to the postfix expression.
✔ If a character is '(', push it onto the stack.
✔ If a character is ')', pop operators from the stack and append to the postfix
expression until '(' is encountered. Discard '('.
✔ If a character is an operator (+, -, *, /):
✔ Pop operators from the stack and append to postfix while the stack is not empty and
the top operator has higher or equal precedence.
✔ Push the current operator onto the stack.
✔ After scanning all characters, pop any remaining operators from the stack and append
to the postfix expression.
✔ The resulting list is the postfix expression.
PYTHON CODE
class InfixToPostfixConverter: self.operator_stack.pop() # Pop the '('
def __init__(self): elif self.is_operator(ch):
self.operator_stack = [] while (self.operator_stack
self.postfix_expression = [] and
def is_operator(self, ch): self.get_precedence(ch) <=
return ch in ['+', '-', '*', '/'] self.get_precedence(self.operator_stack[-
def get_precedence(self, operator): 1])):
if operator in ['+', '-']: self.postfix_expression.append([Link]
return 1 _stack.pop())
elif operator in ['*', '/']: self.operator_stack.append(ch)
return 2 while self.operator_stack:
else: self.postfix_expression.append([Link]
return 0 _stack.pop())
def infix_to_postfix(self, infix): return
for ch in infix: ''.join(self.postfix_expression)
if [Link](): def main():
self.postfix_expression.append(ch) infix_converter =
elif ch == '(': InfixToPostfixConverter()
infix_expression = input("Enter infix
self.operator_stack.append(ch) expression: ")
elif ch == ')': postfix_expression =
while self.operator_stack infix_converter.infix_to_postfix(infix_expre
and self.operator_stack[-1] != '(': ssion)
print(f"Infix: {infix_expression}")
self.postfix_expression.append([Link] print(f"Postfix: {postfix_expression}")
JAVA CODE
import [Link]; StringBuilder postfix = new
import [Link]; StringBuilder();
public class Main { Stack<Character> operatorStack = new
private static boolean isOperator(char Stack<>();
ch) { for (char ch : [Link]())
return ch == '+' || ch == '-' || ch {
== '*' || ch == '/'; if
} ([Link](ch)) {
private static int getPrecedence(char [Link](ch);
operator) { } else if (ch == '(') {
switch (operator) { [Link](ch);
case '+': } else if (ch == ')') {
case '-': while (!
return 1; [Link]() &&
case '*': [Link]() != '(') {
case '/':
return 2; [Link]([Link]());
default: }
return 0; [Link](); // Pop
} the '('
} } else if (isOperator(ch)) {
private static String while (!
infixToPostfix(String infix) { [Link]() && getPrecedence(ch)
[Link]([Link]());
}
[Link](ch);
}
}
while (![Link]()) {
[Link]([Link]());
}
return [Link]();
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter infix expression 1: ");
String infix1 = [Link]();
String postfix1 = infixToPostfix(infix1);
[Link]("Postfix expression 1: " + postfix1);
[Link]();
}
}
EVALUATE POSTFIX EXPRESSION
You are given a postfix expression, and your task is to evaluate it using a stack. A postfix

expression is an arithmetic expression in which the operators come after their operands. For

example, the infix expression "3 + 4" is written as "3 4 +" in postfix notation.

Your goal is to implement a Java program that takes a postfix expression as input, evaluates it

using a stack, and outputs the result.

Examples:

Input: "5 3 4 * +"

Output: 17

Explanation: The given postfix expression represents the infix expression (3 * 4) + 5, which

evaluates to 17.

Input: "7 2 / 4 *"

Output: 14

Explanation: The given postfix expression represents the infix expression (7 / 2) * 4, which

evaluates to 14.
LOGIC
✔ Initialize an empty stack for operands.

✔ Scan the postfix expression from left to right.

✔ For each character:

✔ If it is a digit, push it onto the stack as an operand.

✔ If it is an operator (+, -, *, /), pop two operands from the stack, perform the operation and

push the result back onto the stack.

✔ After scanning the entire expression, the result is the only element left in the stack.
PYTHON CODE
class PostfixEvaluator: result = operators[char](operand1,
def __init__(self): operand2)
self.operand_stack = []
def evaluate_postfix(self, expression):
operators = {'+': lambda x, y: x + self.operand_stack.append(result)
y, return
'-': lambda x, y: x - self.operand_stack.pop()
y, def main():
'*': lambda x, y: x * postfix_evaluator =
y,
PostfixEvaluator()
'/': lambda x, y: x //
y} # Use // for integer division postfix_expression = input("Enter
for char in [Link](): the postfix expression: ")
if [Link](): result =
postfix_evaluator.evaluate_postfix(pos
self.operand_stack.append(int(char)) tfix_expression)
elif char in operators:
operand2 =
print("Result:", result)
self.operand_stack.pop() if __name__ == "__main__":
operand1 = main()
self.operand_stack.pop()
JAVA CODE
import [Link]; case '*':
import [Link]; [Link](operand1 *
public class Main { operand2);
public static int evaluatePostfix(String break;
expression) { case '/’:
Stack<Integer> stack = new [Link](operand1 /
Stack<>(); operand2);
for (char c : break;
[Link]()) { }
if ([Link](c)) { }
}
[Link]([Link](c)); return [Link]();
} else { }
int operand2 = [Link](); public static void main(String[] args) {
int operand1 = [Link](); Scanner scanner = new
switch (c) { Scanner([Link]);
case '+': [Link]("Enter the postfix
[Link](operand1 + expression: ");
operand2); String postfixExpression =
break; [Link]();
case '-': int result =
[Link](operand1 - evaluatePostfix(postfixExpression);
operand2); [Link]("Result: " +
break; result);
BASIC CALCULATOR
Design a basic calculator using a stack data structure. The calculator should be able to

perform addition, subtraction, multiplication, and division operations. Implement the

calculator logic using a stack and provide a simple Java program that takes user input for

arithmetic expressions and outputs the result.

Examples:

Input: 3 + 5 * 2

Output: 13

Input: 8 / 2 - 1

Output: 3
LOGIC:

✔ Initialize two stacks, one for operands (operands) and another for operators

(operators).

✔ Iterate through each character in the input expression from left to right.

✔ If a digit is encountered, convert consecutive digits into a number and push it onto

the operands stack.

✔ If an operator (+, -, *, /) is encountered:

✔ Pop operators from the operators stack and operands from the operands stack while the

top operator on the stack has equal or higher precedence than the current operator.

✔ Evaluate the popped operator and operands, then push the result back onto the

operands stack.

✔ Push the current operator onto the operators stack.

PYTHON CODE
def calculate(expression):
operands = []
operators = []
def precedence(op):
if op in {'+', '-'}:
return 1
elif op in {'*', '/'}:
return 2
else:
return 0
def evaluate():
b = [Link]()
a = [Link]()
op = [Link]()
if op == '+':
result = a + b
elif op == '-':
result = a - b
elif op == '*':
result = a * b
else:
result = a / b
[Link](result)
i = 0
while i < len(expression):
char = expression[i]
if [Link]():
num = int(char)
while i + 1 < len(expression) and expression[i + 1].isdigit():
num = num * 10 + int(expression[i + 1])
i += 1
[Link](num)
elif char in {'+', '-', '*', '/'}:
while operators and precedence(char) <= precedence(operators[-1]):
evaluate()
[Link](char)
i += 1
while operators:
evaluate()
return operands[0]
# Example Usage:
expression1 = "3 + 5 * 2"
expression2 = "8 / 2 - 1"
result1 = calculate(expression1)
result2 = calculate(expression2)
print(f"Input: {expression1}\nOutput: {result1}")
print(f"Input: {expression2}\nOutput: {result2}")
JAVA CODE
import [Link].*; [Link](c);
public class Main { }
public static void main(String[] args) { }
Scanner scanner = new Scanner([Link]); while (![Link]()) {
Stack<Integer> operands = new Stack<>(); evaluate(operands, operators);
Stack<Character> operators = new Stack<>(); }
String input = [Link](); [Link]([Link]());
for (int i = 0; i < [Link](); i++) { }
char c = [Link](i);
if ([Link](c)) { private static int precedence(char c) {
int num = c - '0'; if (c == '+' || c == '-') {
while (i + 1 < [Link]() && return 1;
[Link]([Link](i + 1))) { } else if (c == '*' || c == '/') {
num = num * 10 + ([Link](i + 1) - '0'); return 2;
i++; } else {
} return 0;
[Link](num); }
} else if (c == '+' || c == '-' || c == '*' }
|| c == '/') {
while (![Link]() && precedence(c) private static void evaluate(Stack<Integer>
<= precedence([Link]())) { operands, Stack<Character> operators) {
evaluate(operands, operators); int b = [Link]();
}
int a = [Link]();
char op = [Link]();
int result;
if (op == '+') {
result = a + b;
} else if (op == '-') {
result = a - b;
} else if (op == '*') {
result = a * b;
} else {
result = a / b;
}
[Link](result);
}
}
IMPLEMENT A STACK USING
QUEUES
You are required to implement a stack using queues. A stack is a data structure that follows

the Last In, First Out (LIFO) principle, where the last element added to the stack is the first

one to be removed.

You need to design a stack that supports the following operations:

push(x): Add an element x to the top of the stack.

pop(): Remove the element on the top of the stack and return it.

top(): Return the element on the top of the stack without removing it.

isEmpty(): Return true if the stack is empty, false otherwise.

Use queues to implement the stack.

Stack Operations:
1. Push
2. Pop
3. Top
4. Is Empty
5. Exit
Enter your choice (1-5): 1
Enter element to push: 12
Element 12 pushed onto the stack.
Stack Operations:
1. Push
2. Pop
3. Top
4. Is Empty
5. Exit
Enter your choice (1-5): 2
Popped element: 12
LOGIC

Initialize two queues (queue1 and queue2).

push(x) operation:

Add the element x to the non-empty queue.

pop() operation:

Move all elements except the last one from the non-empty queue to the empty queue.

Remove and return the last element from the non-empty queue.

top() operation:

Perform pop() to retrieve the top element.

Push the top element back onto the stack.

Return the top element.

isEmpty() operation:

Check if both queues are empty.

PYTHON CODE
from queue import Queue [Link]([Link]())
class StackUsingQueues: return [Link]()
def __init__(self): def top(self):
self.queue1 = Queue() if self.is_empty():
self.queue2 = Queue() raise RuntimeError("Stack is
def push(self, x): empty")
# Push the element into the non- top_element = [Link]()
empty queue [Link](top_element) # Push the
if not [Link](): top element back after retrieving it
[Link](x) return top_element
else: def is_empty(self):
[Link](x) return [Link]() and
def pop(self): [Link]()
# Move elements from the non-empty # Example usage:
queue to the empty one, except the last one stack = StackUsingQueues()
if self.is_empty(): [Link](12)
raise RuntimeError("Stack is print("Element 12 pushed onto the stack.")
empty") try:
if not [Link](): popped_element = [Link]()
while [Link]() > 1: print(f"Popped element:
{popped_element}")
[Link]([Link]()) top_element = [Link]()
return [Link]() print(f"Top element: {top_element}")
else: except RuntimeError as e:
while [Link]() > 1: print(f"Error: {e}")
print(f"Is stack empty? {stack.is_empty()}")
JAVA CODE
import [Link];
import [Link];
import [Link];
public class StackUsingQueues {
Queue<Integer> queue1;
Queue<Integer> queue2;
public StackUsingQueues() {
queue1 = new LinkedList<>();
queue2 = new LinkedList<>();
}
public void push(int x) {
// Push the element into the non-empty queue
if (![Link]()) {
[Link](x);
} else {
[Link](x);
}
}
public int pop() {
// Move elements from the non-empty queue to the empty one, except the last one
if ([Link]() && [Link]()) {
throw new RuntimeException("Stack is empty");
}
if (![Link]()) {
while ([Link]() > 1) {
[Link]([Link]());
}
return [Link]();
} else {
while ([Link]() > 1) {
[Link]([Link]());
}
return [Link]();
}
}
public int top() {
int topElement = pop();
push(topElement); // Push the top element back after retrieving it
return topElement;
}
public boolean isEmpty() {
return [Link]() && [Link]();
}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
StackUsingQueues stack = new StackUsingQueues();
while (true) {
[Link]("\nStack Operations:");
[Link]("1. Push");
[Link]("2. Pop");
[Link]("3. Top");
[Link]("4. Is Empty");
[Link]("5. Exit");
[Link]("Enter your choice (1-5): ");
int choice = [Link]();
switch (choice) {
case 1:
[Link]("Enter element to push: ");
int elementToPush = [Link]();
[Link](elementToPush);
[Link]("Element " + elementToPush + " pushed onto the stack.");
break;
case 2:
try {
int poppedElement = [Link]();
[Link]("Popped element: " + poppedElement);
} catch (RuntimeException e) {
[Link]("Error: " + [Link]());
}
break;
case 3:
try {
int topElement = [Link]();
[Link]("Top element: " + topElement);
} catch (RuntimeException e) {
[Link]("Error: " + [Link]());
}
break;
case 4:
[Link]("Is stack empty? " + [Link]());
break;
case 5:
[Link]("Exiting
program.");
[Link]();
[Link](0);
default:
[Link]("Invalid choice.
Please enter a number between 1 and 5.");
}
}
}
}
IMPLEMENT QUEUE USING STACKS
You are required to implement a queue data structure using two stacks. The goal is to simulate

the functionality of a queue, which follows the First-In-First-Out (FIFO) principle, using two

stacks that follow the Last-In-First-Out (LIFO) principle.

Your task is to implement the following operations for the queue:

enqueue(x): Add an element x to the back of the queue.

dequeue(): Remove and return the front element of the queue. If the queue is empty, return -1.

peek(): Return the front element of the queue without removing it. If the queue is empty,

return -1.

isEmpty(): Return true if the queue is empty, false otherwise.

Choose operation:
1. Enqueue
2. Dequeue
3. Check if the queue is empty
4. Exit
1
Enter the element to enqueue:
56
Choose operation:
1. Enqueue
2. Dequeue
3. Check if the queue is empty
4. Exit
1
Enter the element to enqueue:
67
Choose operation:
1. Enqueue
2. Dequeue
3. Check if the queue is empty
4. Exit
3
Is the queue empty? false
 LOGIC

⮚ Initialization:

Create two stacks, stack1 and stack2.

stack1 is used for the enqueue operation.

stack2 is used for the dequeue operation.

⮚ Enqueue Operation:

To enqueue an element, push it onto stack1.

⮚ Dequeue Operation:

If stack2 is not empty, pop from stack2 (since it has the front element).

⮚ If stack2 is empty:

While stack1 is not empty, pop from stack1 and push onto stack2.

Pop from stack2 (now it has the front element).

⮚ Check if Queue is Empty (isEmpty):

Return True if both stack1 and stack2 are empty; otherwise, return False.
PYTHON CODE
class QueueUsingStacks:
def __init__(self):
self.stack1 = [] # Used for enqueue operation
self.stack2 = [] # Used for dequeue operation
def enqueue(self, element):
# Implement enqueue operation using stack1
[Link](element)
def dequeue(self):
# Implement dequeue operation using stack2 if it's not empty, otherwise transfer
elements from stack1 to stack2
if not self.stack2:
while self.stack1:
[Link]([Link]())
# Pop from stack2 to perform dequeue operation
if self.stack2:
return [Link]()
else:
# Queue is empty
print("Queue is empty")
return -1 # Return a default value to indicate an empty queue
def is_empty(self):
# Check if both stacks are empty to determine if the queue is empty
return not self.stack1 and not self.stack2
def main():
queue = QueueUsingStacks()
while True:
print("\nChoose operation:")
print("1. Enqueue")
print("2. Dequeue")
print("3. Check if the queue is empty")
print("4. Exit")
choice = int(input())
if choice == 1:
enqueue_element = int(input("Enter the element to enqueue: "))
[Link](enqueue_element)
elif choice == 2:
dequeued_element = [Link]()
if dequeued_element != -1:
print("Dequeued element:", dequeued_element)
elif choice == 3:
print("Is the queue empty?", queue.is_empty())
elif choice == 4:
break
else:
print("Invalid choice. Please enter a valid option.")
if __name__ == "__main__":
main()
JAVA CODE
import [Link];
import [Link];
class QueueUsingStacks {
private Stack<Integer> stack1; // Used for enqueue operation
private Stack<Integer> stack2; // Used for dequeue operation
public QueueUsingStacks() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void enqueue(int element) {
// Implement enqueue operation using stack1
[Link](element);
}
public int dequeue() {
// Implement dequeue operation using stack2 if it's not empty, otherwise
transfer elements from stack1 to stack2
if ([Link]()) {
while (![Link]()) {
[Link]([Link]());
}
}
 // Pop from stack2 to perform dequeue operation
if (![Link]()) {
return [Link]();
} else {
// Queue is empty
[Link]("Queue is empty");
return -1; // Return a default value to indicate an empty
queue
}
}
public boolean isEmpty() {
// Check if both stacks are empty to determine if the queue is
empty
return [Link]() && [Link]();
}
}
public class Main {
public static void main(String[] args) {
QueueUsingStacks queue = new QueueUsingStacks();
Scanner scanner = new Scanner([Link]);
while (true) {
 [Link]("\nChoose operation:");
[Link]("1. Enqueue");
[Link]("2. Dequeue");
[Link]("3. Check if the queue is empty");
[Link]("4. Exit");
int choice = [Link]();
switch (choice) {
case 1:
[Link]("Enter the element to enqueue:");
int enqueueElement = [Link]();
[Link](enqueueElement);
break;
case 2:
int dequeuedElement = [Link]();
if (dequeuedElement != -1) {
[Link]("Dequeued element: " +
dequeuedElement);
}
break;
case 3:
[Link]("Is the queue empty? " +
[Link]());
break;
case 4:
[Link](0);
break;
default:
[Link]("Invalid choice. Please enter a
valid option.");
}
}
}
}
ZIG ZAG LEVEL ORDER
TRAVERSAL
Given the root node of a tree, print its nodes in zig zag order, i.e. print
the first level left to right, next level right to left, third level left to
right and so on.

Note
You need to complete the given function. The input and printing of output
will be handled by the driver code.
Input Format
The first line of input contains a string represeting the nodes, N is to
show null node.
Output Format
For each test case print the nodes of the tree in zig zag traversal.
Test cases:

Explanation

Example 1 Original tree was:

Input 1
/ \
1 2 3 4 5 6 7 2 3
Output / \ / \
4 5 6 7
1 3 2 4 5 6 7 After Zig Zag traversal, tree formed would be:

1
/ \
3 2
/ \ / \
4 5 6 7
Test cases:

Explanation
Example 2 Original Tree was:
Input
5
5 8 7 / \
8 7
Output
New tree formed is:
5 7 8
5
/ \
7 8
LOGIC
• We use two stacks: currentLevel to store nodes at the current level, and nextLevel
for the next level.
• Start with the root node and push it onto currentLevel.
• While currentLevel is not empty:
• Pop a node from currentLevel.
• Print its data.
• If traversing from left to right, push its left and right children onto nextLevel if
they exist.
• If traversing from right to left, push its right and left children onto nextLevel if
they exist.
• If currentLevel becomes empty, switch the values of currentLevel and nextLevel.
• Repeat until all nodes are traversed.
PYTHON CODE
class Node: else:
def __init__(self, data): if [Link]:
[Link] = data next_level.append([Link])
[Link] = None if [Link]:
[Link] = None next_level.append([Link])
def zigzag_level_order_traversal(root): if not current_level:
if not root: left_to_right = not left_to_right
return current_level, next_level =
current_level = [] next_level, current_level
next_level = [] root = Node(1)
left_to_right = True [Link] = Node(2)
current_level.append(root) [Link] = Node(3)
while current_level: [Link] = Node(4)
node = current_level.pop() [Link] = Node(5)
print([Link], end=" ") [Link] = Node(6)
if left_to_right: [Link] = Node(7)
if [Link]: zigzag_level_order_traversal(root)
next_level.append([Link])
if [Link]:
next_level.append([Link])
JAVA CODE
import [Link]; String currVal = ip[i];
import [Link]; if (![Link]("N")) {
import [Link].*; [Link] = new
import [Link].*; Node([Link](currVal));
class Main { [Link]([Link]);
static Node buildTree(String str) { }
if ([Link]() == 0 || i++;
[Link](0) == 'N') {
return null; if (i >= [Link]) {
} break;
String ip[] = [Link](" "); }
Node root = new currVal = ip[i];
Node([Link](ip[0])); if (![Link]("N")) {
Queue<Node> queue = new [Link] = new
LinkedList<>(); Node([Link](currVal));
[Link](root); [Link]([Link]);
int i = 1; }
while ([Link]() > 0 && i < i++;
[Link]) { }
Node currNode = [Link](); return root;
[Link](); }
public static void main(String[] args) class Solution {
throws IOException { public static void
BufferedReader br = new binaryTreeZigZagTraversal(Node root) {
BufferedReader(new if (root == null) {
InputStreamReader([Link])); return;
String s1 = [Link](); }
Node root1 = buildTree(s1); Stack<Node> currentLevel = new
Solution g = new Solution(); Stack<>();
Stack<Node> nextLevel = new
[Link](root1); Stack<>();
} boolean leftToRight = true;
} [Link](root);
class Node {
int data; while (![Link]()) {
Node left; Node node =
Node right; [Link]();
Node(int data) { [Link]([Link] + " ");
[Link] = data;
left = null; if (leftToRight) {
right = null; if ([Link] != null) {
}
} [Link]([Link]);
}
 if ([Link] != null) { if ([Link]()) {
leftToRight = !
[Link]([Link]); leftToRight;
} Stack<Node> temp =
} else { currentLevel;
if ([Link] != null) { currentLevel = nextLevel;
nextLevel = temp;
[Link]([Link]); }
} }
if ([Link] != null) { }
}
[Link]([Link]);
}
}
SUM ROOT TO LEAF NODES
Given a binary tree, where every node value is a Digit from 1-9. Find the sum of all the

numbers which are formed from root to leaf paths.

For example, consider the following Binary Tree.
6
/ \
3 5
/ \ \
2 5 4
/ \
7 4
There are 4 leaves, hence 4 root to leaf paths:
Path Number
6->3->2 632
6->3->5->7 6357
6->3->5->4 6354
6->5>4 654
Answer = 632 + 6357 + 6354 + 654 = 13997
 LOGIC
Create a Node class to represent the nodes of the binary tree with a value, left, and
right children.
Create a BinaryTree class with a method to calculate the sum of all numbers formed from
root to leaf paths.
In the sum calculation method:
• If the current node is None, return 0.
• Update the running total by multiplying it by 10 and adding the current node's
value.
• If the current node is a leaf, return the updated total.
• Recursively call the method on the left and right children, passing the updated
total.
• The result is the sum of all numbers formed from root to leaf paths.
In the main program, create a BinaryTree instance, build the tree, and call the sum
calculation method with the root node.
Print the result.
PYTHON CODE
class Node: def tree_paths_sum(self, node):
def __init__(self, data): return self.tree_paths_sum_util(node, 0)
[Link] = data # Example usage
[Link] = None tree = BinaryTree()
[Link] = None [Link] = Node(6)
class BinaryTree: [Link] = Node(3)
def __init__(self): [Link] = Node(5)
[Link] = None [Link] = Node(4)
def tree_paths_sum_util(self, node, val): [Link] = Node(2)
if not node: [Link] = Node(5)
return 0 [Link] = Node(4)
val = val * 10 + [Link] [Link] = Node(7)
if not [Link] and not [Link]: print("Sum of all paths is",
return val tree.tree_paths_sum([Link]))
return
(self.tree_paths_sum_util([Link], val) +

self.tree_paths_sum_util([Link], val))
JAVA CODE
class Node { return treePathsSumUtil([Link], val) +
int data; treePathsSumUtil([Link], val);
Node left, right; }
Node(int item) { int treePathsSum(Node node) {
data = item; return treePathsSumUtil(node, 0);
left = right = null; }
}} }
class BinaryTree { public class Main {
Node root; public static void main(String args[]) {
int treePathsSumUtil(Node node, int val) BinaryTree tree = new BinaryTree();
{ [Link] = new Node(6);
if (node == null) [Link] = new Node(3);
return 0; [Link] = new Node(5);
val = (val * 10 + [Link]); [Link] = new Node(4);
if ([Link] == null && [Link] ==
null)
[Link] = new Node(2);
[Link] = new Node(5);
[Link] = new Node(4);
[Link] = new Node(7);
[Link]("Sum of all paths is " + [Link]([Link]));
}
}
BINARY RIGHT SIDE VIEW
You are given a root pointer to the root of binary tree. You have to print the right view of the
tree from top to bottom.
Note
The right view of a tree is the set of nodes that are visible from the right side.
You need to complete the given function. The input and printing of output will be handled by the
driver code.
Input Format
The first line contains the number of test cases.
The second line contains a string giving array representation of a tree, if the root has no
children give N in input.
Output Format
For each test case print the right view of the binary tree.
Example 1
Input
1
1 2 3
1
/ \
2 3
Output
1 3
Explanation
'1' and '3' are visible from the right side.
Example 2
Input:
1
1 2 3 N N 4
1
/ \
2 3
/
4
Output
1 3 4
Explanation
'1', '3', and '4' are visible from the right side.
LOGIC
1. Initialize an empty queue.
2. Enqueue the root of the tree.
3. While the queue is not empty:
Get the size of the current level (`level_size`).
Traverse the nodes at the current level:
Dequeue a node from the front of the queue.
If it is the last node in the level, add its value to the result (rightmost node).
Enqueue its left and right children (if they exist).
4. Return the result, which contains the values of the rightmost nodes at each level.
PYTHON CODE
from collections import deque
class Node:
def __init__(self, data):
[Link] = data
[Link] = None
[Link] = None
class Solution:
def rightView(self, root):
result = []
if not root:
return result
queue = deque()
[Link](root)
while queue:
level_size = len(queue)
for i in range(level_size):
current = [Link]()
if i == level_size - 1:
[Link]([Link])
if [Link]:
[Link]([Link])
if [Link]:
[Link]([Link])
return result
def buildTree(arr):
if not arr or arr[0] == 'N':
return None
root = Node(int(arr[0]))
queue = deque([root])
i = 1
while queue and i < len(arr):
current_node = [Link]()

if arr[i] != 'N':
current_node.left = Node(int(arr[i]))
[Link](current_node.left)
i += 1
if i < len(arr) and arr[i] != 'N':
current_node.right = Node(int(arr[i]))
[Link](current_node.right)
i += 1
return root
if __name__ == "__main__":
t = int(input())
for _ in range(t):
s = input().split()
root = buildTree(s)
tree = Solution()
arr = [Link](root)
for x in arr:
print(x, end=" ")
print()
JAVA CODE
import [Link]; if (root == null) {
import [Link]; return list;
import [Link]; }
import [Link];
Queue<Node> q = new LinkedList<>();
import [Link];
[Link](root);
import [Link];
while (![Link]()) {
class Node { int n = [Link]();
int data; for (int i = 0; i < n; i++) {
Node left; Node curr = [Link]();
Node right; if (i == n - 1) {
[Link]([Link]);
Node(int data) { }
[Link] = data; if ([Link] != null) {
left = null; [Link]([Link]);
}
right = null;
if ([Link] != null) {
} [Link]([Link]);
} }
class Solution { } }
ArrayList<Integer> rightView(Node return list;
root) { }}
ArrayList<Integer> list = new
ArrayList<>();
public class Main { i++;
static Node buildTree(String str) {
if ([Link]() == 0 || [Link](0) if (i >= [Link])
== 'N') { break;
return null;
} currVal = ip[i];
if (![Link]("N")) {
String[] ip = [Link](" "); [Link] = new
Node root = new Node([Link](currVal));
Node([Link](ip[0])); [Link]([Link]);
Queue<Node> queue = new }
LinkedList<>(); i++;
[Link](root); }
int i = 1; return root;
}
while (![Link]() && i <
[Link]) { public static void main(String[] args)
Node currNode = [Link](); throws IOException {
BufferedReader br = new
String currVal = ip[i]; BufferedReader(new
if (![Link]("N")) { InputStreamReader([Link]));
[Link] = new int t =
Node([Link](currVal)); [Link]([Link]());
[Link]([Link]);
}
 while (t-- > 0) {
String s = [Link]();
Node root = buildTree(s);
Solution tree = new Solution();
ArrayList<Integer> arr = [Link](root);
for (int x : arr)
[Link](x + " ");
[Link]();
}
}
}
DIAMETER OF BINARY TREE
Given a root of a binary tree, write a function to get the diameter of the tree. The diameter of
a binary tree is the length of the longest path between any two nodes in a tree. This path may or
may not pass through the root.

Input Format
You are given a string s which describes the nodes of the binary tree. (The first element
corresponds to the root, the second is the left child of the root and so on). In the function,
you are provided with the root of the binary tree.

Output Format
Return the diameter of the binary tree.
Example 1
Input

8 2 1 3 N N 5
Output

5
Explanation

The longest path is between 3 and 5. The diameter is 5.

Example 2
Input

1 2 N
Output

2
Explanation

The longest path is between 1 and 2. The diameter is 2.

LOGIC
1. The diameter of a binary tree is the length of the longest path between
any two nodes.
2. This path may or may not pass through the root.
3. To find the diameter, we need to find the height of the left and right
subtrees for each node.
4. The diameter at a particular node is the sum of the height of the left
and right subtrees plus 1 (for the current node).
5. The diameter of the entire tree is the maximum diameter among all
nodes.
PYTHON CODE
class TreeNode: def diameter(self, root):
def __init__(self, value): if not root:
[Link] = value return 0
[Link] = None self.height_and_diameter(root)
[Link] = None return [Link]
class Solution: # Example usage
def __init__(self): tree = TreeNode(8)
[Link] = 0 [Link] = TreeNode(2)
def height_and_diameter(self, root): [Link] = TreeNode(1)
if not root: [Link] = TreeNode(3)
return 0 [Link] = None
left_height = [Link] = None
self.height_and_diameter([Link]) [Link] = TreeNode(5)
right_height = solution = Solution()
self.height_and_diameter([Link]) print("Diameter of the binary tree:",
# Update diameter for the current [Link](tree))
node
[Link] = max([Link], left_height
+ right_height + 1)
# Return height of the current
subtree
return 1 + max(left_height,
right_height)
JAVA CODE
import [Link]; [Link]();
import [Link]; String currVal = ip[i];
import [Link].*; if (![Link]("N")) {
import [Link].*; [Link] = new
Node([Link](currVal));
class Main {
[Link]([Link]);
static Node buildTree(String str) { }
if ([Link]() == 0 || i++;
[Link](0) == 'N') { if (i >= [Link]) break;
return null; currVal = ip[i];
} if (![Link]("N")) {
String ip[] = [Link](" "); [Link] = new
Node root = new Node([Link](currVal));
Node([Link](ip[0])); [Link]([Link]);
Queue<Node> queue = new }
LinkedList<>(); i++;
}
[Link](root);
return root;
int i = 1; }
while ([Link]() > 0 && i < public static void main(String[] args)
[Link]) { throws IOException {
Node currNode = [Link]();
 BufferedReader br =new BufferedReader(new class Solution {
InputStreamReader([Link])); static int height(Node root, A a) {
String s1 = [Link](); if (root == null) {
Node root1 = buildTree(s1); return 0;
Solution g = new Solution(); }
[Link]([Link](root1)); int left = height([Link], a);
} int right = height([Link], a);
} [Link] = [Link]([Link], left + right +
class Node { 1);
int data; return 1 + [Link](left, right);
Node left; }
Node right; public static int diameter(Node root) {
Node(int data) { if (root == null) {
[Link] = data; return 0;
left = null; }
right = null; A a = new A();
} height(root, a);
} return [Link];
class A }
{ }
int ans = 0;
}
FLATTEN BINARY TREE TO LINKED
LIST
Flatten Binary Tree To Linked List. Write a program that flattens a given binary tree to a linked
list.

Note:

The sequence of nodes in the linked list should be the same as that of the preorder traversal of
the binary tree.
The linked list nodes are the same binary tree nodes. You are not allowed to create extra nodes.
The right child of a node points to the next node of the linked list whereas the left child
points to NULL.
Example
Reverse Preorder traversal

Root’s left tree became the right tree

New right tree’s rightmost node points to root’s right tree
Solution steps —

Process right sub-tree

Process left sub-tree
Process root
Make the left node as a right node of the root
Set right node as a right node of the new right sub-tree
Set left node to NULL
LOGIC
1. Start at the root of the tree.
2. For each node in the tree:
a. If the node has a left child:
* Find the rightmost node in the left subtree.
* Move the right subtree of the current node to the right of the rightmost node in the left
subtree.
* Set the left subtree as the new right subtree.
* Set the left child to null.
b. Move to the next node using the right pointer.

This process rearranges the connections in the tree, effectively turning it into a linked list. The
linked list retains the order of nodes as if traversing the tree in a preorder fashion.
PYTHON CODE
class TreeNode:
def __init__(self, value):
[Link] = value
[Link] = None
[Link] = None
def flatten(root):
if not root:
return
current = root
while current:
if [Link]:
# Find the rightmost node in the left subtree
rightmost = [Link]
while [Link]:
rightmost = [Link]
# Move the right subtree of the current node to the rightmost node
in the left subtree
[Link] = [Link]
# Set the left subtree as the new right subtree
[Link] = [Link]
# Set the left child to null
[Link] = None
# Move to the next node in the modified tree
current = [Link]
def print_linked_list(root):
while root:
print([Link], '*>', end=' ')
root = [Link]
print('null')
# Example usage:
# Constructing a sample binary tree
root = TreeNode(1)
[Link] = TreeNode(2)
[Link] = TreeNode(5)
[Link] = TreeNode(3)
[Link] = TreeNode(4)
[Link] = TreeNode(6)
# Flatten the binary tree to a linked list
flatten(root)
# Print the linked list
print_linked_list(root)
JAVA CODE
class TreeNode {
int val;
TreeNode left, right;

public TreeNode(int value) {

val = value;
left = right = null;
}
}

public class FlattenBinaryTreeToLinkedList {

public static void flatten(TreeNode root) {
if (root == null) {
return;
}

TreeNode current = root;

while (current != null) {
if ([Link] != null) {
// Find the rightmost node in the left subtree
TreeNode rightmost = [Link];
while ([Link] != null) {
rightmost = [Link];
}

// Move the right subtree of the current node

to the rightmost node in the left subtree
[Link] = [Link];

// Set the left subtree as the new right

subtree
[Link] = [Link];

// Set the left child to null

[Link] = null;
}

// Move to the next node in the modified tree

current = [Link];
} }
public static void printLinkedList(TreeNode root) {
while (root != null) {
[Link]([Link] + " -> ");
root = [Link];
}
[Link]("null");
}
public static void main(String[] args) {
// Example usage:
// Constructing a sample binary tree
TreeNode root = new TreeNode(1);
[Link] = new TreeNode(2);
[Link] = new TreeNode(5);
[Link] = new TreeNode(3);
[Link] = new TreeNode(4);
[Link] = new TreeNode(6);
// Flatten the binary tree to a linked list
flatten(root);
// Print the linked list
printLinkedList(root);
}
}
LOWEST COMMON ANCESTOR
Given the root node of a tree, whose nodes have their values in the range of integers. You are
given two nodes x, y from the tree. You have to print the lowest common ancestor of these nodes.

Lowest common ancestor of two nodes x, y in a tree or directed acyclic graph is the lowest node
that has both nodes x, y as its descendants.

Your task is to complete the function findLCA which receives the root of the tree, x, y as its
parameters and returns the LCA of these values.
Input Format:
The first line contains the values of the nodes of the tree in the level order form.

The second line contains two integers separated by space which denotes the nodes x and y.

Output Format:
Print the LCA of the given nodes in a single line.
Example 1
Input

1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
7 5
Output

1
Explanation

1
/ \
2 3
/ / \
4 5 6
\
7
The root of the tree is the deepest node which contains both the nodes 7 and 5 as
its descendants, hence 1 is the answer.
Example 2
Input
1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1
4 2
Output
2
Explanation

1
/ \
2 3
/ / \
4 5 6
\
7
The node will value 2 of the tree is the deepest node which contains both the nodes 4 and 2 as
its descendants, hence 2 is the answer.
LOGIC
1. Perform a recursive traversal of the tree.
2. If the current node is one of the given nodes (`n1` or `n2`), return the
current node.
3. Recursively search for the LCA in the left and right subtrees.
4. If both left and right subtrees return non-null values, the current node
is the LCA.
5. Return the LCA found during the traversal.
PYTHON CODE
class Node: curr_node.right = Node(int(curr_val))
def __init__(self, key): [Link](curr_node.right)
[Link] = key i += 1
[Link] = None return root
[Link] = None def find_lca(root, n1, n2):
def build_tree(arr): if root is None:
if not arr or arr[0] == "N": return None
return None if [Link] == n1 or [Link] == n2:
root = Node(int(arr[0])) return root
queue = [root] left_lca = find_lca([Link], n1, n2)
i = 1 right_lca = find_lca([Link], n1,
while queue and i < len(arr): n2)
curr_node = [Link](0) if left_lca is not None and right_lca
curr_val = arr[i] is not None:
if curr_val != "-1": return root
curr_node.left = return left_lca if left_lca is not
Node(int(curr_val)) None else right_lca
[Link](curr_node.left) # Input
i += 1 s = input().split()
if i >= len(arr): root = build_tree(s)
break x, y = map(int, input().split())
curr_val = arr[i] # Find LCA
if curr_val != "-1": ans = find_lca(root, x, y)
print([Link] if ans else "N")
JAVA CODE
 [Link]();
import [Link]; String currVal = ip[i];
import [Link]; if (![Link]("-1")) {
import [Link].*; [Link] = new
import [Link].*; Node([Link](currVal));
class Main { [Link]([Link]);
static Node buildTree(String str) { }
if ([Link]() == 0 || i++;
[Link](0) == 'N') { if (i >= [Link]) break;
return null; currVal = ip[i];
} if (![Link]("-1")) {
String ip[] = [Link](" "); [Link] = new
Node root = new Node([Link](currVal));
Node([Link](ip[0])); [Link]([Link]);
Queue<Node> queue = new }
LinkedList<>(); i++;
[Link](root); }
int i = 1;
while ([Link]() > 0 && i < [Link]) return root;
{ }
Node currNode = [Link]();
 public static void main(String[] args) class Solution {
throws IOException { public static Node findLCA(Node
Scanner sc = new node,int n1,int n2) {
Scanner([Link]); if (node == null)
String s = [Link](); return null;
Node root = buildTree(s);
int x = [Link](); if ([Link] == n1 || [Link]
int y = [Link](); == n2)
Solution g = new Solution(); return node;
Node ans = [Link](root,x,y); Node left_lca = findLCA([Link],
[Link]([Link]); n1, n2);
} Node right_lca =
} findLCA([Link], n1, n2);
class Node { if (left_lca != null &&
int data; right_lca != null)
Node left; return node;
Node right; return (left_lca != null) ?
Node(int data) { left_lca : right_lca;
[Link] = data; }
left = null; }
right = null;
}}
VALIDATE BINARY SEARCH TREE
Given a binary tree with N number of nodes, check if that input tree is BST (Binary Search Tree)
or not. If yes, print true, print false otherwise. A binary search tree (BST) is a binary tree
data structure which has the following properties.

• The left subtree of a node contains only nodes with data less than the node’s data.

• The right subtree of a node contains only nodes with data greater than the node’s data.

• Both the left and right subtrees must also be binary search trees.
Input Format
The first line contains an Integer 't', which denotes the number of
test cases or queries to be run. Then the test cases follow.
The first line of input contains the elements of the tree in the level
order form separated by a single space.
If any node does not have a left or right child, take -1 in its place.

Output Format
For each test case, print true if the binary tree is a BST, else print
false.

Output for every test case will be denoted in a separate line.

Example 1
Input
1
3 1 5 -1 2 -1 -1 -1 -1
Output
true
Explanation
Level 1: For node 3 all the nodes in the left subtree (1,2) are less than 3 and all the nodes in
the right subtree (5) are greater than 3.
Level 2: For node 1: The left subtree is empty and all the nodes in the right subtree (2) are
greater than 1.
For node 5: Both right and left subtrees are empty.
Level 3: For node 2, both right and left subtrees are empty. Because all the nodes follow the
property of a binary search tree, the function should return true.
Example 2
Input

1
3 2 5 1 4 -1 -1 -1 -1 -1 -1
Output

false
Explanation

For the root node, all the nodes in the right subtree (5) are greater than 3. But node with data
4 in the left subtree of node 3 is greater than 3, this does not satisfy the condition for the
binary search tree. Hence, the function should return false.
LOGIC

1. Traverse the binary tree in a recursive manner.

2. At each node, check whether its data lies within the range (min_val, max_val).
3. For the left subtree, the maximum value is updated to the current node's data, and for the
right subtree, the minimum value is updated.
4. Continue the traversal until all nodes are checked, and return True if all nodes satisfy the
BST conditions, otherwise False.
PYTHON CODE
class BinaryTreeNode: # Input handling
def __init__(self, data): t = int(input())
[Link] = data for _ in range(t):
[Link] = None elements = list(map(int,
[Link] = None input().split()))
n = len(elements)
def validate_bst(root, min_val=float('- tree = [BinaryTreeNode(elements[i]) if
inf'), max_val=float('inf')): elements[i] != -1 else None for i in
if not root: range(n)]
return True i, j = 0, 1
if not min_val <= [Link] <= while i < n:
max_val: if tree[i] is not None:
return False tree[i].left = tree[j]
left_search = validate_bst([Link], j += 1
min_val, [Link]) tree[i].right = tree[j]
right_search = j += 1
validate_bst([Link], [Link], i += 1
max_val) # Check if the tree is a valid BST
print(validate_bst(tree[0]))
return left_search and right_search
JAVA CODE
import [Link].*; // An empty tree is a BST
class BinaryTreeNode<T> { if (root == null)
public T data; {
public BinaryTreeNode<T> left; return true;
public BinaryTreeNode<T> right; }

BinaryTreeNode(T data) { // If this node violates the

[Link] = data; min/max constraint
left = null; if (([Link] <= min) ||
right = null; ([Link] >= max))
} {
} return false;
}
public class Main {
boolean leftSearch =
public static boolean helper([Link], min, [Link]);
helper(BinaryTreeNode<Integer> root, int boolean rightSearch =
min, int max) helper([Link], [Link], max);
{
return leftSearch & rightSearch;
}
 public static boolean if([Link](str_arr[i])!=-1)
validateBST(BinaryTreeNode<Integer> root) tree[i] = new
{ BinaryTreeNode([Link](str_arr[i]
return helper(root, ));
Integer.MIN_VALUE, Integer.MAX_VALUE); else
} tree[i] = null;
}
public static void main(String[] int i=0,j=1;
args) throws Throwable { while(i<n)
Scanner sc = new {
Scanner([Link]); if(tree[i] != null)
int t = [Link](); {
[Link](); tree[i].left =
while(t>0) tree[j];
{ j++;
t--; tree[i].right =
String str=[Link](); tree[j];
String[] str_arr = [Link](" j++;
"); }
int n = str_arr.length; i++;
BinaryTreeNode<Integer>[] tree }
= new BinaryTreeNode[n];
for(int i=0;i<n;i++) [Link](validateBST(tree[0]));
{ }
Kth SMALLEST ELEMENT IN A BST
Given a binary search tree (BST) and an integer k, find k-th smallest element.
Input:
BST:

2
/ \
1 3
k=3
Output: 3
The 3rd smallest element is 3.
Notes
Input Format: There are two arguments in the input. First one is the root of the
BST and second one is an integer k.
Output: Return an integer, the k-th smallest element of the BST.
LOGIC

1. Perform an in-order traversal of the BST.

2. During the traversal, maintain a count of visited nodes (`result[0]`).

3. When the count equals `k`, store the value of the current node as the k-th

smallest element (`result[1]`).

4. Continue the traversal until the count reaches `k`.

PYTHON CODE
class TreeNode: kth_smallest_helper([Link], k,
def __init__(self, val=0, left=None, result)
right=None):
[Link] = val
[Link] = left # Create a sample BST
[Link] = right root = TreeNode(2)
[Link] = TreeNode(1)
def kth_smallest(root, k): [Link] = TreeNode(3)
result = [0, 0]
kth_smallest_helper(root, k, result)
# Set the value of k
return result[1]
def kth_smallest_helper(root, k, result): k = 3
if root is None:
return # Find the k-th smallest element in
kth_smallest_helper([Link], k, the BST
result) result = kth_smallest(root, k)
# Visit the current node
result[0] += 1
print(f"The {k}-th smallest element
if result[0] == k: is: {result}")
result[1] = [Link]
return
JAVA CODE
class TreeNode { // Find the k-th smallest element in the
int val; BST
TreeNode left, right; int result = kthSmallest(root, k);

public TreeNode(int val) { [Link]("The " + k + "-

[Link] = val; th smallest element is: " + result);
[Link] = [Link] = null; }
}
} public static int kthSmallest(TreeNode
root, int k) {
public class Main { int[] result = new int[2];
kthSmallestHelper(root, k,
public static void main(String[] args) result);
{ return result[1];
// Create a sample BST }
TreeNode root = new TreeNode(2);
[Link] = new TreeNode(1); private static void
[Link] = new TreeNode(3); kthSmallestHelper(TreeNode root, int k,
int[] result) {
// Set the value of k if (root == null) {
int k = 3; return;
}
 kthSmallestHelper([Link], k, result);

// Visit the current node

if (++result[0] == k) {
result[1] = [Link];
return;
}

kthSmallestHelper([Link], k, result);
}
}
CONVERT SORTED LIST TO BST
Given a Singly Linked List which has data members sorted in ascending order. Construct a

Balanced Binary Search Tree which has same data members as the given Linked List.
Input: Linked List 1->2->3

Output: A Balanced BST

2
/ \
1 3
Input: Linked List 1->2->3->4->5->6->7

Output: A Balanced BST

4
/ \
2 6
/ \ / \
1 3 5 7
Input: Linked List 1->2->3->4
Output: A Balanced BST
3
/ \
2 4
/
1

Input: Linked List 1->2->3->4->5->6

Output: A Balanced BST
4
/ \
2 6
/ \ /
1 3 5
LOGIC
Count the Number of Nodes:
A helper function countNodes is used to count the number of nodes in the
linked list.

Recursive Construction of BST:

The main function sortedListToBST calculates the number of nodes (n) in the
linked list and calls the recursive function sortedListToBSTRecur with this
count.

Base Case:
If n is less than or equal to 0, return None (base case).
Recursive Calls:
Recursively construct the left subtree (left) by calling sortedListToBSTRecur
on the first half of the linked list.
Create the root of the current subtree with the data of the current head node.
Move the head pointer to the next node in the linked list.
Recursively construct the right subtree (right) by calling sortedListToBSTRecur
on the second half of the linked list.

Return the Root:

Return the root of the current subtree.
Linked List Modification:
The head pointer is modified during the process to simulate traversing the
linked list.
Print the Pre-order Traversal
The preOrder function is used to print the pre-order traversal of the
constructed BST.

Driver Code:
The push function is used to add elements to the linked list, and the main code
initializes the linked list with values, constructs the BST, and prints the
pre-order traversal.
PYTHON CODE
class LinkedList: def sortedListToBSTRecur(self, n):
def __init__(self): if n <= 0:
[Link] = None return None
class LNode: left = [Link](n // 2)
def __init__(self, data): root = [Link]([Link])
[Link] = data [Link] = left
[Link] = None [Link] = [Link]
[Link] = None [Link] = [Link](n
class TNode: - n // 2 - 1)
def __init__(self, data): return root
[Link] = data def countNodes(self, head):
[Link] = None count = 0
[Link] = None temp = head
def sortedListToBST(self): while temp is not None:
n = [Link]([Link]) temp = [Link]
return [Link](n) count += 1
return count
def push(self, new_data): if __name__ == "__main__":
new_node = [Link](new_data) llist = LinkedList()
new_node.prev = None [Link](7)
new_node.next = [Link] [Link](6)
if [Link] is not None: [Link](5)
[Link] = new_node [Link](4)
[Link] = new_node [Link](3)
def printList(self, node): [Link](2)
while node is not None: [Link](1)
print([Link], end=" ") print("Given Linked List ")
node = [Link] [Link]([Link])
def preOrder(self, node): root = [Link]()
if node is None: print("\nPre-Order Traversal of constructed BST
return ")
print([Link], end=" ") [Link](root)
[Link]([Link])
[Link]([Link])
JAVA CODE
class LinkedList { TNode sortedListToBST() {
static LNode head; int n =
class LNode { countNodes(head);
int data; return
LNode next, prev; sortedListToBSTRecur(n);
LNode(int d) { }
data = d;
next = prev = null; TNode sortedListToBSTRecur(int n)
}} {
class TNode { if (n <= 0)
int data; return null;
TNode left, right;
TNode(int d) { TNode left = sortedListToBSTRecur(n / 2);
data = d; TNode root = new TNode([Link]);
left = right = null; [Link] = left;
}} head = [Link];
[Link] = sortedListToBSTRecur(n - n / 2 new_node.prev = null;
- 1); new_node.next = head;
return root; if (head != null)
} [Link] = new_node;
int countNodes(LNode head) { head = new_node;
int count = 0; }
LNode temp = head; void printList(LNode node) {
while (temp != null) { while (node != null) {
temp = [Link]; [Link]([Link] + " ");
count++; node = [Link];
} }
return count; }
} void preOrder(TNode node) {
void push(int new_data) { if (node == null)
LNode new_node = new LNode(new_data); return;
[Link]([Link] + " "); [Link](1);
preOrder([Link]); [Link]("Given Linked List ");
preOrder([Link]); [Link](head);
} TNode root = [Link]();
public static void main(String[] args) { [Link]("");
LinkedList llist = new [Link]("Pre-Order
LinkedList(); Traversal of constructed BST ");
[Link](7); [Link](root);
[Link](6); }
[Link](5); }
[Link](4);
[Link](3);
[Link](2);
DEPTH-FIRST SEARCH
You are given a graph represented as an adjacency list. Implement the Depth-
First Search (DFS) algorithm to traverse the graph and return the order in
which the nodes are visited.
Depth first Search or Depth first traversal is a recursive algorithm
for searching all the vertices of a graph or tree data structure

A standard DFS implementation puts each vertex of the graph into one
of two categories:

1. Visited
2. Not Visited

The purpose of the algorithm is to mark each vertex as visited while

avoiding cycles.
Step1: Initially stack and visited arrays are empty.
Step 2: Visit 0 and put its adjacent nodes which are not visited yet
into the stack.
Step 3: Now, Node 1 at the top of the stack, so visit node 1
and pop it from the stack and put all of its adjacent nodes
which are not visited in the stack.
Step 4: Now, Node 2 at the top of the stack, so visit node 2
and pop it from the stack and put all of its adjacent nodes
which are not visited (i.e, 3, 4) in the stack.
Step 5: Now, Node 4 at the top of the stack, so visit node 4
and pop it from the stack and put all of its adjacent nodes
which are not visited in the stack.
Step 6: Now, Node 3 at the top of the stack, so visit node 3 and pop
it from the stack and put all of its adjacent nodes which are not
visited in the stack.
Now, Stack becomes empty, which means we have visited all the nodes
and our DFS traversal ends.
LOGIC

DFS(G, u)
[Link] = true
for each v ∈ [Link][u]
if [Link] == false
DFS(G,v)

init() {
For each u ∈ G
[Link] = false
For each u ∈ G
DFS(G, u)
}
PYTHON CODE
from collections import defaultdict for adj in [Link][vertex]:
class Graph: if not [Link][adj]:
def __init__(self, vertices): [Link](adj)
[Link] = defaultdict(list) if __name__ == "__main__":
[Link] = [False] * vertices g = Graph(4)
def addEdge(self, src, dest): [Link](0, 1)
[Link][src].append(dest) [Link](0, 2)
def DFS(self, vertex): [Link](1, 2)
[Link][vertex] = True [Link](2, 3)
print(vertex, end=" ") print("Following is Depth First
Traversal")
[Link](2)
JAVA CODE
import [Link].*; void addEdge(int src, int dest) {
class Graph { adjLists[src].add(dest);
private LinkedList<Integer> }// DFS algorithm
adjLists[]; void DFS(int vertex) {
private boolean visited[]; visited[vertex] = true;
// Graph creation [Link](vertex + " ");
Graph(int vertices) { Iterator<Integer> ite =
adjLists = new adjLists[vertex].listIterator();
LinkedList[vertices]; while ([Link]()) {
visited = new boolean[vertices]; int adj = [Link]();
for (int i = 0; i < vertices; i+ if (!visited[adj])
+) DFS(adj);
adjLists[i] = new } }
LinkedList<Integer>();
public static void main(String args[]) {
Graph g = new Graph(4);

[Link](0, 1);
[Link](0, 2);
[Link](1, 2);
[Link](2, 3);

[Link]("Following is Depth First Traversal");

[Link](2);
}
}
PRIM’S ALGORITHM
Given a weighted graph, we have to find the minimum spanning tree (MST) of that graph
using Prim’s algorithm. Print the final weight of the MST.

Input Format
The first line contains one integer v representing the number of nodes.

Next lines contains a v*v matrix representing the graph. matrix[i][j] represents the
value of the weight between the ith node and the jth node. If there is no edge, the
value is 0.

Output Format
Print the final weight of the MST.
Example 1
Input

5
0 2 0 6 0
2 0 3 8 5
0 3 0 0 7
6 8 0 0 9
0 5 7 9 0
Output

16
Explanation

Edge Weight
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
Total sum = 16
Example 2
Input

5
0 4 2 0 0
4 0 1 3 0
2 1 0 7 2
0 3 7 0 5
0 0 2 5 0
Output

8
Explanation

Edge Weight
2 - 1 1
0 - 2 2
1 - 3 3
2 - 4 2
Total sum = 8
LOGIC
1. Initialize:
Create an array `key[]` to store the key values of vertices, initially set to
`INFINITY` except for the first vertex, which is set to 0.
Create an array `parent[]` to store the parent (or the vertex that leads to the
minimum key value) for each vertex.
Create a boolean array `mstSet[]` to represent whether a vertex is included in the
MST or not.
Initialize all keys as `INFINITY`, set the first key to 0, and set all elements in
`mstSet[]` as `false`.
2. Select Vertices:
Repeat the following until all vertices are included in the MST:
a. Choose the vertex `u` with the minimum key value from the set of vertices not
yet included in the MST (`mstSet[]` is `false`).
b. Include `u` in the MST by setting `mstSet[u]` to `true`.
c. Update the key values of all adjacent vertices of `u` if they are not included
in the MST and the weight of the edge (`graph[u][v]`) is less than the current key value
of the vertex `v`.
3. Print MST:
Print the sum of the key values of all vertices in the MST.
This sum represents the weight of the minimum spanning tree.
This logic using adjacency lists to represent the graph. It
initializes key values, updates them during the algorithm's
execution, and prints the final weight of the MST.
PYTHON CODE
import sys print(total_sum)
def minKey(key, mstSet, V): def primMST(graph):
min_val = [Link] V = len(graph)
min_index = -1 parent = [-1] * V
for v in range(V): key = [[Link]] * V
if not mstSet[v] and key[v] < mstSet = [False] * V
min_val: key[0] = 0
min_val = key[v] parent[0] = -1
min_index = v for _ in range(V - 1):
return min_index u = minKey(key, mstSet, V)
def printMST(parent, graph): mstSet[u] = True
V = len(graph) for v in range(V):
total_sum = 0 if graph[u][v] != 0 and not
for i in range(1, V): mstSet[v] and graph[u][v] < key[v]:
total_sum += graph[i][parent[i]]
parent[v] = u
key[v] = graph[u][v]

printMST(parent, graph)

# Input
V = int(input())
graph = [list(map(int, input().split())) for _ in
range(V)]

# Execute Prim's Algorithm

primMST(graph)
JAVA CODE
import [Link].*; static void printMST(int parent[],
class Solution{ List<List<Integer>> graph) {
static int minKey(int key[], boolean int V = [Link]();
mstSet[], int V) { int sum = 0;
int min = Integer.MAX_VALUE, for (int i = 1; i < V; i++) {
min_index = -1; sum +=
for (int v = 0; v < V; v++) { [Link](i).get(parent[i]);
if (!mstSet[v] && key[v] < min) }
{ [Link](sum);
min = key[v]; }
min_index = v; static void primMST(List<List<Integer>>
} graph) {
} int V = [Link]();
return min_index; int parent[] = new int[V];
} int key[] = new int[V];
boolean mstSet[] = new boolean[V]; parent[v] = u;
for (int i = 0; i < V; i++) { key[v] =
key[i] = Integer.MAX_VALUE; [Link](u).get(v);
mstSet[i] = false; }
} }
key[0] = 0; }
parent[0] = -1; printMST(parent, graph);
for (int count = 0; count < V - 1; }
count++) { }
int u = minKey(key, mstSet, V); public class Main {
mstSet[u] = true; public static void main(String[] args) {
for (int v = 0; v < V; v++) { Scanner sc = new Scanner([Link]);
if ([Link](u).get(v) != 0 int V = [Link]();
&& !mstSet[v] && [Link](u).get(v) < List<List<Integer>> graph = new
key[v]) { ArrayList<>();
for (int i = 0; i < V; i++) {
List<Integer> temp = new ArrayList<>(V);
for (int j = 0; j < V; j++) {
[Link]([Link]());
}
[Link](temp);
}
[Link](graph);
[Link]();
}
}
MINIMUM FUEL COST TO REPORT
TO THE CAPITAL
There is a tree (i.e., a connected, undirected graph with no cycles) structure country
network consisting of n cities numbered from 0 to n - 1 and exactly n - 1 roads. The
capital city is city 0. You are given a 2D integer array roads where roads[i] = [ai, bi]
denotes that there exists a bidirectional road connecting cities ai and bi.
There is a meeting for the representatives of each city. The meeting is in the capital
city.
There is a car in each city. You are given an integer seats that indicates the number of
seats in each car.
A representative can use the car in their city to travel or change the car and ride with
another representative. The cost of traveling between two cities is one liter of fuel.

Return the minimum number of liters of fuel to reach the capital city.
Example 1:

Input: roads = [[3,1],[3,2],[1,0],[0,4],[0,5],[4,6]], seats

= 2
Output: 7

Explanation:

⮚ Representative2 goes directly to city 3 with 1 liter of

fuel.
⮚ Representative2 and representative3 go together to city 1
with 1 liter of fuel.
⮚ Representative2 and representative3 go together to the
capital with 1 liter of fuel.
⮚ Representative1 goes directly to the capital with 1 liter
of fuel.
⮚ Representative5 goes directly to the capital with 1 liter
of fuel.
⮚ Representative6 goes directly to city 4 with 1 liter of
fuel.
⮚ Representative4 and representative6 go together to the
capital with 1 liter of fuel.
Example 2:

Input: roads = [[0,1],[0,2],[0,3]], seats = 5

Output: 3

Explanation:

⮚ Representative1 goes directly to the capital with 1

liter of fuel.
⮚ Representative2 goes directly to the capital with 1
liter of fuel.
⮚ Representative3 goes directly to the capital with 1
liter of fuel.
⮚ It costs 3 liters of fuel at minimum. It can be proven
that 3 is the minimum number of liters of fuel needed.
LOGIC
Initialization:

An ArrayList adj is created to represent an adjacency list for a graph. It's used to
store the connections between different nodes (roads).
Graph Construction:

The roads array is used to construct an undirected graph (adjacency list). Each road
connection is added to the adj list.
Recursive DFS (Depth-First Search):

The solve function is a recursive DFS function that explores the graph, calculating the
number of people in each subtree.
The base case is when a leaf node is reached, i.e., a node with only one connection.
Fuel Cost Calculation:
For each node (except the root), the fuel cost is calculated based on the number of
people in the subtree and the number of seats available. The cost is added to the global
variable ans.
Main Function:

The minimumFuelCost function initializes the adj list, calls the solve function to
calculate the fuel cost, and returns the final result.
Example Usage:

An example is provided where roads are defined, and the minimum fuel cost is calculated
for a given number of seats.
PYTHON CODE
from math import ceil for i in adj[src]:
class Solution: if i != parent:
def __init__(self): people += [Link](adj, seats, i,
[Link] = 0 src)
def minimum_fuel_cost(self, roads, if src != 0:
seats): [Link] += ceil(people / seats)
adj = [[] for _ in range(len(roads) + return people
1)] # Example Usage
n = len(roads) + 1 solution = Solution()
[Link] = 0 roads = [[3, 1], [3, 2], [1, 0], [0, 4], [0,
for a, b in roads: 5], [4, 6]]
adj[a].append(b) seats = 2
adj[b].append(a) result = solution.minimum_fuel_cost(roads,
[Link](adj, seats, 0, -1) seats)
return [Link] print(result)
def solve(self, adj, seats, src,
JAVA CODE
import [Link]; solve(adj, seats, 0, -1);
public class Solution { return ans;
private long ans = 0L; }
public long minimumFuelCost(int[][] roads, private long
int seats) { solve(ArrayList<ArrayList<Integer>> adj, int
ArrayList<ArrayList<Integer>> adj = new seats, int src, int parent) {
ArrayList<>(); long people = 1L;
int n = [Link] + 1; for (int i : [Link](src)) {
ans = 0L; if (i != parent) {
for (int i = 0; i < n; i++) { people += solve(adj, seats, i,
[Link](new ArrayList<>()); src);
} }
for (int[] a : roads) { }
[Link](a[0]).add(a[1]); if (src != 0) {
[Link](a[1]).add(a[0]); ans += (long) [Link]((double)
} people / seats);
}
return people;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[][] roads = {{3, 1}, {3, 2}, {1, 0}, {0, 4}, {0, 5}, {4, 6}};
int seats = 2;
long result = [Link](roads, seats);
[Link](result);
}
}
NUMBER OF ISLANDS
You are given a 2D matrix grid of size n * m. You have to find the number of distinct
islands where a group of connected 1s (horizontally or vertically) forms an island. Two
islands are considered to be distinct if and only if one island is not equal to another
(rotated or reflected islands are not euqal).

Input Format
The first line contains two integers value of N and M.

Next N line contains M boolean values where 1 denotes land and 0 denotes water.

Output Format
Print total number of distinct islands.
Example 1
Input

3 4
1 1 0 0
0 0 0 1
1 1 1 0
Output

3
Explanation

There are only 3 distinct islands.

1 1 in row 1
1 in row 2
down right
1 1 1 in row 3
Example 2
Input

3 4
1 1 0 0
0 0 0 1
0 1 1 0
Output

2
Explanation

There are 3 islands once again, but island in row 1 and row 3 are not distinct,
hence only 2 distinct islands.
LOGIC
Initialize Variables:

Define the directions to move (up, left, down, right).

Initialize a set to store the distinct islands' coordinates.
DFS Function:

Implement a DFS function that explores the connected land cells of an island.
Mark visited cells as -1 to indicate they have been processed.
Traverse the Grid:

Iterate through each cell in the grid.

If the cell is part of an unexplored island (grid value is 1), initiate DFS from
that cell.
Coordinate Transformation:

Convert the island coordinates to a tuple and add it to the set.

Count Distinct Islands:

The size of the set represents the count of distinct islands.

PYTHON CODE
def count_distinct_islands(grid): for j in range(cols):
def dfs(x0, y0, i, j, v): if grid[i][j] != 1:
nonlocal grid continue
rows, cols = len(grid), len(grid[0]) v = []
if i < 0 or i >= rows or j < 0 or j dfs(i, j, i, j, v)
>= cols or grid[i][j] <= 0: [Link](tuple(v))
return return len(coordinates)
grid[i][j] *= -1 # Input handling
[Link]((i - x0, j - y0)) n, m = map(int, input().split())
for k in range(4): grid = [list(map(int, input().split())) for
dfs(x0, y0, i + dirs[k][0], j + _ in range(n)]
dirs[k][1], v) dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]]
rows, cols = len(grid), len(grid[0]) # Call the function to count distinct
coordinates = set() islands
for i in range(rows): ans = count_distinct_islands(grid)
print(ans)
JAVA CODE
import [Link].*; for (int k = 0; k < 4; k++) {
class Solution { dfs(grid, x0, y0, i + dirs[k][0], j
static int[][] dirs = {{0, -1}, {-1, 0}, {0, + dirs[k][1], v);
1}, {1, 0}}; }
private static String toString(int r, int c) }
{ public static int countDistinctIslands(int[]
return [Link](r) + " " + [] grid) {
[Link](c); int rows = [Link];
} if (rows == 0)
private static void dfs(int[][] grid, int return 0;
x0, int y0, int i, int j, ArrayList<String> v) { int cols = grid[0].length;
int rows = [Link], cols = if (cols == 0)
grid[0].length; return 0;
if (i < 0 || i >= rows || j < 0 || j >= HashSet<ArrayList<String>> coordinates =
cols || grid[i][j] <= 0) new HashSet<>();
return; for (int i = 0; i < rows; ++i) {
grid[i][j] *= -1;
[Link](toString(i - x0, j - y0));
for (int j = 0; j < cols; ++j) { int n = [Link]();
if (grid[i][j] != 1) int m = [Link]();
continue; int[][] grid = new int[n][m];
ArrayList<String> v = new for (int i = 0; i < n; i++) {
ArrayList<>(); for (int j = 0; j < m; j++) {
dfs(grid, i, j, i, j, v); grid[i][j] = [Link]();
[Link](v); }
} }
} Solution ob = new Solution();
return [Link](); int ans = [Link](grid);
} [Link](ans);
} }
public class Main { }
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
COURSE SCHEDULE
You are given a number N, the number of courses you have to take labeled from 0 t N-1.
You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that
you must take course bi first if you want to take course ai.
eg: [2,4] means take course 4 before you can take course 2.

Input Format
The First line of input contain two integers N denoting number of people and M denoting
size of prerequisites array.

Next line contains two integer each denoting ai and bi.

Output Format
print 1 if it is possible to finish all the courses else print 0.
Example 1
Input

4 3
1 2
1 3
1 0
Output

1
Explanation

We need to take course 2,3 and 0 before taking course 1.

Since no conflict is there, we can take it.
Example 2
Input

4 3
1 2
2 3
3 1
Output

Now, let's analyze the prerequisites:

Course 2 (index 1) must be taken before course 1 (index 0).

Course 3 (index 2) must be taken before course 2 (index 1).
Course 1 (index 0) must be taken before course 3 (index 2).
If we visualize this as a graph, it forms a cycle: 1 -> 2 -> 3 -> 1. This cycle
indicates a circular dependency, and it is not possible to finish all the courses
without violating the prerequisites. In this case, the output should be 0.
LOGIC
1. Build a graph and calculate in-degrees for each course.

2. Initialize a set with courses having no prerequisites.

3. Perform BFS by removing courses with no prerequisites, updating in-degrees, and

adding new courses with no prerequisites.

4. If all courses are taken (sum of in-degrees is 0), return 1; otherwise, return 0.

5. The result indicates whether it is possible to finish all courses based on the

given prerequisites.
PYTHON CODE
from collections import defaultdict if degree[neighbor] == 0:
class Solution:
def canFinish(self, n, prerequisites): no_prerequisites.add(neighbor)
G = defaultdict(list) return int(sum(degree) == 0)
degree = [0] * n # Input handling
for e in prerequisites: N, M = map(int, input().split())
G[e[1]].append(e[0]) prerequisites = [list(map(int,
degree[e[0]] += 1 input().split())) for _ in range(M)]
no_prerequisites = set(i for i in # Call the solution class
range(n) if degree[i] == 0) Obj = Solution()
while no_prerequisites: print([Link](N, prerequisites))
course = no_prerequisites.pop()
for neighbor in G[course]:
degree[neighbor] -= 1
JAVA CODE
import [Link].*;
class Solution {
public int canFinish(int n, int[][] prerequisites) {
ArrayList<Integer>[] G = new ArrayList[n];
int[] degree = new int[n];
ArrayList<Integer> bfs = new ArrayList();
for (int i = 0; i < n; ++i) G[i] = new ArrayList<Integer>();
for (int[] e : prerequisites) {
G[e[1]].add(e[0]);
degree[e[0]]++;
}
for (int i = 0; i < n; ++i) if (degree[i] == 0) [Link](i);
for (int i = 0; i < [Link](); ++i)
for (int j: G[[Link](i)])
if (--degree[j] == 0) [Link](j);
if([Link]() == n)
 return 1;
else
return 0;
}}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int N= [Link]();
int M= [Link]();
int prerequisites[][] = new int[M][2];
for(int i=0; i<M; i++){
for(int j=0; j<2; j++)
prerequisites[i][j]= [Link]();
}
Solution Obj = new Solution();
[Link]([Link](N,prerequisites));
}
}
LETTER COMBINATIONS OF
A PHONE NUMBER
Given a string containing digits from 2-9 inclusive, print all possible
letter combinations that the number could represent. Print the answer in
sorted order.
A mapping of digit to letters (just like on the telephone buttons) is
given below.
Note
1 does not map to any letters.
2 : abc
3 : def
4 : ghi
5 : jkl
6 : mno
7 : pqrs
8 : tuv
9 : wxyz
Input Format
The first line of input contains a string of digits.

Output Format
Print all possible letter combinations that the number could represent,
separated by spaces.

Print the answer in sorted order.

Test cases:

Example 2
Example 1
Input
Input
2
23 Output
Output
a b c
ad ae af bd be bf cd ce cf Explanation
Explanation
2 maps to a, b, c.

2 maps to any of a,b,c

whereas 3 maps to any of
d,e,f. Hence 9 possible
combinations.
LOGIC
Base Case:

If the input string s is empty, print the current combination (ans).

This is the stopping condition for the recursion.
Recursive Step:

Get the mapping (key) of the first digit in the input string s.
For each character in the mapping:
Recursively call the function with the remaining digits (s[1:]) and the
updated combination (ans + char).
The recursion will continue until the base case is reached.
Mapping (keypad) Explanation:

The keypad array is used to map each digit to the corresponding letters on a
telephone keypad.
For example, keypad[2] corresponds to "abc," keypad[3] corresponds to "def,"
and so on.
PYTHON CODE
def possible_words(s, ans):
# Base Case
if not s:
print(ans)
return

# Get the mapping of the first digit

key = keypad[int(s[0])]

# Recursive Step
for char in key:
# Recursively call the function with the remaining digits and updated combination
possible_words(s[1:], ans + char)

# Corrected initialization of keypad

keypad = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]

# Input handling
s = input("Enter a string of digits: ")

# Call the function to print possible letter combinations

print("Possible letter combinations:")
possible_words(s, "")
JAVA CODE
import [Link]; public static void main (String[] args) {
Scanner scan=new Scanner([Link]);
public class Main{ String s=[Link]();
static String[] possibleWords(s,"");
keypad={"","","abc","def","ghi","jkl","mno","p }
qrs","tuv","wxyz"}; }

static void possibleWords(String s,String ans)

{
if([Link]()==0){
[Link](ans);
return;
}

String key= keypad[[Link](0)-48];

for(int i=0;i<[Link]();i++){

possibleWords([Link](1),ans+[Link](i)
);
}

}
PERMUTATIONS
Problem Statement: Generating Permutations using Backtracking

Given a set of distinct integers, write a program to generate all possible permutations
of the elements in the set.
Example:

Suppose the input set is {1, 2, 3}.

The program should output the following permutations:

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
LOGIC

Base Case:
• If the left index is equal to the right index, print the current permutation.

Recursion:
• Iterate through each element from the left index to the right index.
• Swap the current element with the element at index 'i'.
• Recursively generate permutations for the remaining elements.
• Backtrack by undoing the swap to restore the original order.
PYTHON CODE
def generate_permutations(nums, left, right): # Backtrack: Undo the swap to restore the
if left == right: original order
# Base case: Print the current nums[left], nums[i] = nums[i],
permutation nums[left]
print(nums)
else: # Input handling
for i in range(left, right + 1): n = int(input("Enter the number of elements in
# Swap the current element with the the set: "))
element at index 'i' nums = list(map(int, input("Enter the elements
nums[left], nums[i] = nums[i], of the set: ").split()))
nums[left]
# Call the function to generate permutations
# Recursively generate permutations print("Permutations of the set:")
for the remaining elements generate_permutations(nums, 0, n - 1)
generate_permutations(nums, left +
1, right)
JAVA CODE
import [Link]; [Link]("Permutations of the set:");
public class PermutationsBacktracking { generatePermutations(nums, 0, n - 1);
public static void main(String[] args) { [Link]();
Scanner scanner = new Scanner([Link]); }
// Get input from the user private static void generatePermutations(int[] nums, int
[Link]("Enter the number of elements in the left, int right) {
set: "); if (left == right) {
int n = [Link](); // Base case: Print the current permutation
int[] nums = new int[n]; printArray(nums);
[Link]("Enter the elements of the set:"); } else {
for (int i = 0; i < n; i++) { for (int i = left; i <= right; i++) {
nums[i] = [Link]();
}
// Swap the current element with the element private static void swap(int[] nums, int i,
at index 'i' int j) {
swap(nums, left, i); int temp = nums[i];
nums[i] = nums[j];
// Recursively generate nums[j] = temp;
permutations for the remaining elements }
generatePermutations(nums, private static void printArray(int[]
left + 1, right); nums) {
// Backtrack: Undo the swap for (int num : nums) {
to restore the original order [Link](num + " ");
swap(nums, left, i); }
} [Link]();
}} }
}
COMBINATION SUM
Given an array of distinct integers nums and a target integer target,
return a list of all unique combinations of nums where the chosen
numbers sum to target. You may return the combinations in any order.

The same number may be chosen from nums an unlimited number of times.
Two combinations are unique if the frequency of at least one of the
chosen numbers is different.
Input Format
Input is managed for you. (You are given an array nums and target
target in the combinationSum() function).

Output Format
Output is managed for you. (You can return the possible valid
combinations in any order. The combinations will be automatically
printed in sorted order).
Example 1
Input
4 16
6 2 7 5
Output
2 2 2 2 2 2 2 2
2 2 2 2 2 6
2 2 2 5 5
2 2 5 7
2 2 6 6
2 7 7
5 5 6
Explanation

Here all these combinations have sum equal to 16.

(2 2 2 2 2 2 2 2)
(2 2 2 2 2 6)
(2 2 2 5 5)
(2 2 5 7)
(2 2 6 6)
(2 7 7)
(5 5 6)
Example 2
Input

3 5
1 2 3
Output

1 1 1 1 1
1 1 1 2
1 1 3
1 2 2
2 3
Explanation

Here all these combinations have sum equal to 5.

(1 1 1 1 1)
(1 1 1 2)
(1 1 3)
(1 2 2)
(2 3)
LOGIC
⮚ Sort the array nums to handle duplicates and for easier comparison
later.
⮚ Use a backtracking function to explore all possible combinations,
keeping track of the current combination in the tempList.
⮚ If the current combination sums up to the target, add it to the
result list.
⮚ Recursively call the backtracking function for each element in the
array, allowing duplicates to be reused.
⮚ Sort the result list and its sublists for proper ordering, and print
the unique combinations.
PYTHON CODE
class Solution: # Input handling
def combinationSum(self, nums, target): n, target = map(int, input().split())
[Link]()
nums = list(map(int,
result = []
[Link](result, [], nums, input().split()))
target, 0)
return result # Call the solution class
ob = Solution()
def backtrack(self, result, tempList, ans = [Link](nums, target)
nums, remain, start):
if remain < 0:
return # Sort the result
elif remain == 0: [Link](key=lambda x: (len(x), x))
[Link]([Link]())
else: # Print the result
for i in range(start, for combination in ans:
len(nums)):
[Link](nums[i])
print(*combination)
[Link](result,
tempList, nums, remain - nums[i], i)
[Link]()
JAVA CODE
import [Link].*; [Link](nums[i]);
class Solution { backtrack(list, tempList, nums, remain -
nums[i], i); // not i + 1 because we can
public List<List<Integer>> reuse same elements
combinationSum(int[] nums, int target) { [Link]([Link]()
List<List<Integer>> list = new - 1);
ArrayList<>(); }
[Link](nums); }
backtrack(list, new ArrayList<>(), }
nums, target, 0); }
return list; public class Main {
} public static void main(String args[])
{
private void backtrack(List<List<Integer>> Scanner sc = new
list, List<Integer> tempList, int [] nums, Scanner([Link]);
int remain, int start){ int n = [Link]();
if(remain < 0) return; int target = [Link]();
else if(remain == 0){ int []nums = new int[n];
[Link](new for(int i = 0 ; i < n ; ++i){
ArrayList<>(tempList)); nums[i] = [Link]();
} }
else{
for(int i = start; i < [Link];
i++){
Solution ob = new Solution();
List<List<Integer>> ans = [Link](nums,target);
for(int i = 0 ; i < [Link]() ; ++i){
[Link]([Link](i));
}
[Link](ans, (o1, o2) -> {
int m = [Link]([Link](), [Link]());
for (int i = 0; i < m; i++) {
if ([Link](i) == [Link](i)){
continue;
}else{
return [Link](i) - [Link](i);
}
}
return 1;
});
for (int i = 0; i < [Link] (); i++)
{
for (int j = 0; j < [Link](i).size (); j++)
{
[Link]([Link](i).get(j)+" ");
}
[Link]();

}}}
GENERATE PARENTHESES
Given a positive integer n, write a function to generate all combinations of well-formed
parentheses. The goal is to generate all possible combinations of parentheses such that
they are balanced.

A well-formed parentheses string is defined as follows:

The empty string is well-formed.

If "X" is a well-formed parentheses string, then "(X)" is also well-formed.
If "X" and "Y" are well-formed parentheses strings, then "XY" is also well-formed.
Example
n = 3, the function should return the following
combinations:

[ "((()))", "(()())", "(())()", "()(())", "()()()"]

Your task is to implement the solution in Java using

backtracking and take the input n from the user.
LOGIC
1. Start with an empty string.
2. If the count of open parentheses is less than n, add an open parenthesis and
recursively call the function.
3. If the count of close parentheses is less than the count of open
parentheses, add a close parenthesis and recursively call the function.
4. If the length of the current string is equal to 2 * n, add it to the result.
5. Repeat these steps recursively, exploring all possible combinations.
PYTHON CODE
def generate_parenthesis(n): generate_parenthesis_helper(0, 0, "")
result = [] return result
def # Get input from the user
generate_parenthesis_helper(open_count, n = int(input("Enter the value of n: "))
close_count, current): combinations = generate_parenthesis(n)
nonlocal result
if len(current) == 2 * n: print(f"Combinations of well-formed
[Link](current) parentheses for n = {n}:")
return for combination in combinations:
if open_count < n: print(combination)

generate_parenthesis_helper(open_count + 1,
close_count, current + "(")
if close_count < open_count:

generate_parenthesis_helper(open_count,
JAVA CODE
import [Link]; if ([Link]() == 2 * n) {
import [Link]; [Link](current);
import [Link]; return;
public class GenerateParentheses { }
public static List<String> if (openCount < n) {
generateParenthesis(int n) { generateParenthesisHelper(n,
List<String> result = new openCount + 1, closeCount, current + "(",
ArrayList<>(); result);
generateParenthesisHelper(n, 0, 0, }
"", result); if (closeCount < openCount) {
return result; generateParenthesisHelper(n,
} openCount, closeCount + 1, current + ")",
private static void result);
generateParenthesisHelper(int n, int }
openCount, int closeCount, String current, }
List<String> result) {
 public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter the value of n: ");
int n = [Link]();
List<String> combinations = generateParenthesis(n);
[Link]("Combinations of well-formed parentheses for n = " + n +
":");
for (String combination : combinations) {
[Link](combination);
}
}
}
LONGEST HAPPY PREFIX
A string is called a happy prefix if is a non-empty prefix which is also a suffix
(excluding itself).

Given a string s. Return the longest happy prefix of s .

Return an empty string if no such prefix exists.

Example 1:

Input: s = "level"
Output: "l"
Explanation: s contains 4 prefix excluding itself ("l", "le", "lev", "leve"),
and suffix ("l", "el", "vel", "evel"). The largest prefix which is also suffix
is given by "l".
Example 2:

Input: s = "ababab"
Output: "abab"
Explanation: "abab" is the largest prefix which is also suffix. They can overlap
in the original string.
LOGIC
1. Prefix and Suffix Matching:

• Iterate through the string from left to right.

• Keep track of the length of the matching prefix and suffix.

• Whenever a matching character is found, increment the length.

2. Check for Happy Prefix:

• If at any point the current matching prefix length is equal to the length of

the string minus one, it means we have a happy prefix.

• The reason is that a happy prefix cannot include the entire string, so the

length of the matching prefix should be less than the length of the string.
PYTHON CODE
def longest_happy_prefix(s): # Return the longest happy prefix
n = len(s)
return s[:length]
# Compute the prefix function using KMP
# Get input from the user
algorithm
input_str = input("Enter a string: ")
prefix_function = [0] * n
j = 0 # Find and print the longest happy
for i in range(1, n): prefix
while j > 0 and s[i] != s[j]: result =
j = prefix_function[j - 1]
longest_happy_prefix(input_str)
if s[i] == s[j]:
print("Longest Happy Prefix:",
j += 1
prefix_function[i] = j
result)

# The length of the longest happy prefix

is given by the last value in the prefix
function
length = prefix_function[-1]
JAVA CODE
public class LongestHappyPrefix { }
public static String }
longestHappyPrefix(String s) { }
int n = [Link](); int happyPrefixLength = lps[n - 1];
int[] lps = new int[n]; return happyPrefixLength > 0 ?
int len = 0; [Link](0, happyPrefixLength) : "";
for (int i = 1; i < n; ) { }
if ([Link](i) == public static void main(String[] args) {
[Link](len)) {
lps[i++] = ++len; [Link](longestHappyPrefix("level
} else { "));
if (len != 0) { }
len = lps[len - 1]; }
} else {
lps[i++] = 0;
LONGEST SUBSTRING WITHOUT
REPEATING CHARACTERS
You are given a string s. Your task is to find the length of the longest substring that
contains each character at most once.

A substring is a contiguous sequence of characters within a string.

Input Format
First line contains the string s.

Output Format
Complete the function longestSubstring() where you return the required integer.
Example 1
Input

xyzxyzyy
Output

3
Explanation

The answer is "xyz ", with the length of 3

Example 2

Input
xxxxxx

Output
1
LOGIC
✔ We use a sliding window approach to find the longest substring without
repeating characters.
✔ Maintain two pointers, start and end, representing the current substring.
✔ Use a dictionary (char_index_map) to keep track of the last index of each
character encountered.
✔ If a character is already in the current substring, update the start index to
the next index of the previous occurrence of that character.
✔ Update the last index of the current character in the char_index_map.
✔ Update the length of the current substring and keep track of the maximum
length encountered.
PYTHON CODE
def longestSubstring(s): char_index_map[s[end]] = end
char_index_map = {} # To store the last # Update the length of the current
index of each character substring
start = 0 # Start index of the current max_length = max(max_length, end -
substring start + 1)
max_length = 0 # Length of the longest return max_length
substring input_str2 = "xxxxxx"
for end in range(len(s)): result2 = longestSubstring(input_str2)
if s[end] in char_index_map and print("Output:", result2) # Output: 1
char_index_map[s[end]] >= start:
# If the character is already in
the current substring, update the start
index
start = char_index_map[s[end]] +
1
# Update the last index of the
JAVA CODE
import [Link].*; res = [Link](res, right - left + 1);
class Solution { right++;
public int longestSubstring(String s) { }
Map<Character, Integer> chars = new return res;
HashMap(); }}
int left = 0; public class Main {
int right = 0; public static void main (String[] args)
int res = 0; throws [Link] {
while (right < [Link]()) { Scanner sc=new Scanner([Link]);
char r = [Link](right); String s = [Link]();
[Link](r, [Link](r,0) + Solution ob = new Solution();
1); int ans=[Link](s);
while ([Link](r) > 1) { [Link](ans);
char l = [Link](left); }
[Link](l, [Link](l) - }
1);
LONGEST PALINDROMIC SUBSTRING
Given a string s, find the longest palindromic substring in s.

Example:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Input: "cbbd"
Output: "bb"
LOGIC
PYTHON CODE
def longest_palindromic_substring(s):
if right1 - left1 > end - start:
def expand_around_center(left, right):
start, end = left1, right1
while left >= 0 and right < len(s)
if right2 - left2 > end - start:
and s[left] == s[right]:
start, end = left2, right2
left -= 1
right += 1
return s[start:end + 1]
return left + 1, right - 1
# Get input from the user
start, end = 0, 0
input_str = input("Enter a string: ")
for i in range(len(s)):
# Find and print the longest palindromic
left1, right1 =
substring
expand_around_center(i, i) # Odd-length
result =
palindrome
longest_palindromic_substring(input_str)
left2, right2 =
print("Longest Palindromic Substring:",
expand_around_center(i, i + 1) # Even-
result)
length palindrome
JAVA CODE
import [Link]; palindrom[i][j] = true;
class LongestPalindromicSubstring { if(j-i+1 > longestSoFar) {
private static String longestSoFar = j-i+1;
findLongestPalindromicSubstring(String startIndex = i;
input) { endIndex = j;
if([Link]()) { } } } }
return ""; return [Link](startIndex,
} endIndex+1);
int n = [Link](); }
int longestSoFar = 0, startIndex = 0, public static void main(String[] args) {
endIndex = 0; Scanner keyboard = new
boolean[][] palindrom = new boolean[n] Scanner([Link]);
[n]; String input = [Link]();
for(int j = 0; j < n; j++) { [Link](findLongestPalindromicSub
palindrom[j][j] = true; string(input));
for(int i = 0; i < j; i++) { }
SHORTEST PALINDROME
Problem Statement:
Given a string, find the shortest palindrome that can be obtained by adding characters
in front of it.
Example 1:
Input: "race"
Output: "ecarace"
Explanation: By adding "eca" in front of "race," we get the shortest palindrome
"ecarace."

Example 2:
Input: "abc"
Output: "cba"
Explanation: By adding "cba" in front of "abc," we get the shortest palindrome "cbaabc."

Example 3:
Input: "level"
Output: "level"
Explanation: The given string "level" is already a palindrome, so no additional
Input: "abc" Output: "cbaabc"

LOGIC
⮚ Iterate from the end of the string, considering each prefix.
Start from the end of the string "abc."
Consider each prefix, trying to find the longest palindrome.
Consider the prefix "cba" from "abc."
⮚ The prefix "cba" is a palindrome.
Reverse the remaining suffix "abc" and append it to the original string.
⮚ Reverse "abc" to get "cba."
Append the reversed suffix to the original string.
Result: "cbaabc"
So, by adding the palindrome "cba" in front of the original string "abc" and then
appending the reversed suffix "abc," we get the shortest palindrome "cbaabc."
PYTHON CODE
def shortest_palindrome(s):
def is_palindrome(string):
return string == string[::-1]
for i in range(len(s), 0, -1):
prefix = s[:i]
if is_palindrome(prefix):
suffix = s[i:]
return suffix[::-1] + s
return s
# Get input from the user
input_str = input("Enter a string: ")

# Find and print the shortest palindrome

result = shortest_palindrome(input_str)
print("Shortest Palindrome:", result)
JAVA CODE
import [Link];
public class Main {
public static String shortestPalindrome(String s) {
if (s == null || [Link]()) {
return "";
}
int i = 0;
for (int j = [Link]() - 1; j >= 0; j--) {
if ([Link](i) == [Link](j)) {
i++;
}}
if (i == [Link]()) {
return s;
}
String suffix = [Link](i);
String prefix = new StringBuilder(suffix).reverse().toString();
String middle = shortestPalindrome([Link](0, i));

return prefix + middle + suffix;

}
public static void main(String[] args) {
Scanner scanner = new Scanner([Link]);
[Link]("Enter a string: ");
String input = [Link]();
String result = shortestPalindrome(input);
[Link]("Shortest Palindrome: " + result);
[Link]();
}
}
MINIMUM DELETIONS TO MAKE ARRAYS
DIVISIBLE
You are given two positive integer arrays nums and numsDivide. You can delete any number
of elements from nums.

Return the minimum number of deletions such that the smallest element in nums divides
all the elements of numsDivide. If this is not possible, return -1.

Note that an integer x divides y if y % x == 0.

Example 1:
Input: nums = [2,3,2,4,3], numsDivide = [9,6,9,3,15]
Output: 2
Explanation:
The smallest element in [2,3,2,4,3] is 2, which does not divide all the elements of
numsDivide.
We use 2 deletions to delete the elements in nums that are equal to 2 which makes nums =
[3,4,3].
The smallest element in [3,4,3] is 3, which divides all the elements of numsDivide.
It can be shown that 2 is the minimum number of deletions needed.
Example 2:

Input: nums = [4,3,6], numsDivide = [8,2,6,10]

Output: -1
Explanation:
We want the smallest element in nums to divide all the elements of numsDivide.
There is no way to delete elements from nums to allow this.
LOGIC
1. Find the greatest common divisor (gcd) of elements in numsDivide.

2. Identify the smallest element in nums that is a divisor of the gcd.

3. If such an element is found, count the number of elements in nums that are different from this

smallest divisor.

4. Return the count obtained in step 3 as the minimum number of deletions.

5. This logic ensures that the smallest divisor is selected to minimize the deletions needed for the

array to satisfy the given conditions.

PYTHON CODE
def min_operations(nums, nums_divide):
def gcd(a, b):
while b > 0:
a, b = b, a % b
return a
g = nums_divide[0]
for i in nums_divide:
g = gcd(g, i)
smallest = float('inf')
for num in nums:
if g % num == 0:
smallest = min(smallest, num)
if smallest == float('inf'):
return -1 # No element in nums can divide all elements in nums_divide
min_op = sum(1 for num in nums if num == smallest)
return min_op
nums1 = [2, 3, 2, 4, 3]
nums_divide1 = [9, 6, 9, 3, 15]
print(min_operations(nums1, nums_divide1)) # Output: 2
JAVA CODE
public class Main { int minOp = 0;
public static int minOperations(int[] nums, for (int num : nums) {
int[] numsDivide) { if (num > smallest) {
int g = numsDivide[0]; ++minOp;
for (int i : numsDivide) { }
g = gcd(g, i); }
} return minOp;
int smallest = Integer.MAX_VALUE; }
for (int num : nums) { private static int gcd(int a, int b) {
if (g % num == 0) { while (b > 0) {
smallest = [Link](smallest, int tmp = a;
num); a = b;
}} b = tmp % b;
if (smallest == Integer.MAX_VALUE) { }
return -1; // No element in nums return a;
can divide all elements in numsDivide }
}
public static void main(String[] args) {
// Example 1
int[] nums1 = {2, 3, 2, 4, 3};
int[] numsDivide1 = {9, 6, 9, 3, 15};
[Link](minOperations(nums1, numsDivide1)); // Output: 2
}
}
FIND IN MOUNTAIN ARRAY
An array is said to be a mountain array if it satisfies the following conditions:

The length of the given array is should be greater or equal to 3 i.e. LENGTH >=3.
There must be only one peak in the array or the largest element in the array.
The array must follows the condition: ARRAY[0] < ARRAY[1] < ARRAY[i-1] < ARRAY[ i] >
ARRAY[ i+1 ] > ARRAY[..] > ARRAY[length-1]
The task is to find the peak index of the mountain array.

Suppose we have given the input [60, 20, 90, 110, 10].

The output will be 3. Because the largest element in the array is 110 whose index is 3.
LOGIC
def find_peak_index(arr):
left, right = 0, len(arr) - 1

while left < right:

mid = (left + right) // 2

if arr[mid] > arr[mid + 1]:

right = mid
else:
left = mid + 1

return left
PYTHON CODE
def find_peak_index(arr):
left, right = 0, len(arr) - 1
while left < right:
mid = left + (right - left) // 2
if arr[mid] < arr[mid + 1]:
left = mid + 1
else:
right = mid
# At the end, left and right will be equal
return left
def main():
n = int(input("Enter the length of the array: "))
arr = list(map(int, input("Enter the elements of the array separated by spaces:
").split()))
peak_index = find_peak_index(arr)
print("The peak index is:", peak_index)
if __name__ == "__main__":
main()
JAVA CODE
import [Link]; Scanner scanner = new Scanner([Link]);
public class Main { [Link]("Enter the length
public static int findPeakIndex(int[] arr) { of the array: ");
int left = 0; int n = 0;
int right = [Link] - 1; while (![Link]()) {
while (left < right) { [Link]("Invalid input.
int mid = left + (right - left) / 2; Please enter a valid integer.");
if (arr[mid] < arr[mid + 1]) { [Link](); // consume the
left = mid + 1; invalid input
} else { }
right = mid; n = [Link]();
}} [Link]("Enter the elements of
return left; // or right, they are equal the array separated by spaces: ");
at the end int[] arr = new int[n];
} for (int i = 0; i < n; i++) {
public static void main(String[] args) { while (![Link]()) {
[Link]("Invalid input. Please enter a valid integer.");
[Link](); // consume the invalid input
}
arr[i] = [Link]();
}
int peakIndex = findPeakIndex(arr);
[Link]("The peak index is: " + peakIndex);
[Link]();
}
}
NUMBER OF SUBSTRING CONTAINS ALL
THREE CHARACTERS
Print the number of substrings containing all three characters i.e. a,b,c at least once
in a given string.

Test Case
Input:
1
acbaa
Output:
5

Explanation:
The substrings containing at least one occurrence of the characters a, b and c are acb,
acba, acbaa, cba and cbaa.
LOGIC
1. initialize pointers start and end to define a substring.
2. Iterate through the string using these pointers.
3. Use an array hash_count to count occurrences of each character in the
substring.
4. Check if the substring contains at least one occurrence of each of
'a', 'b', and 'c'.
5. If yes, update the count with the number of substrings that can be
formed with the remaining characters.
6. Move the pointers accordingly.
7. Print the count for each test case.
PYTHON CODE
def countSubstringsWithABC():
test_cases = int(input("Enter the number of test cases: "))
while test_cases > 0:
S = input("Enter the string: ")
start, end, count = 0, 0, 0
if len(S) < 3:
count = 0
else:
while end < len(S):
hash_count = [0] * 26
for i in range(start, end):
hash_count[ord(S[i]) - ord('a')] += 1
if all(count > 0 for count in hash_count[:3]):
count += len(S) - end + 1
start += 1
else:
end += 1
print(count)
test_cases -= 1
# Example usage:
countSubstringsWithABC()
JAVA CODE
import [Link]; while (test_cases != 0) {
public class Main { [Link]("Enter the
public static void main(String args[]) { string:");
Scanner sc = new Scanner([Link]); String S = [Link]();
int test_cases = 0; int start = 0, end = 0, count =
while (true) { 0;
try { if ([Link]() < 3)
[Link]("Enter the number count = 0;
of test cases:"); else {
test_cases = [Link](); while (end < [Link]()) {
break; int hash[] = new
} catch ([Link] int[26];
e){ for (int i = start; i < end; i++)
[Link]("Invalid {
input. Please enter a valid integer."); hash[[Link](i) - 'a']++;
[Link](); }
count += [Link]() - end + 1;
start++;
} else {
end++;
}
}
}

[Link](count);
test_cases--;
}
}
}
TRAPPING RAIN WATER
Trapping Rain Water

Given with n non-negative integers representing an elevation map where the width

of each bar is 1, we need to compute how much water it is able to trap after

raining.
 Explanation : trap “3 units” of
arr[] = {3, 0, 2, 0, 4}.
water between 3 and 2, “1 unit”
Three units of water can be stored in two indexes
on top of bar 2 and “3 units”
1 and 3, and one unit of water at index 2.
between 2 and 4.
Water stored in each index = 0 + 3 + 1 + 3 + 0

= 7
LOGIC
1. Iterate Through Bars:
Iterate through each bar from the second to the secondtolast bar
2. Find Left and Right Boundaries:
For each bar at index `i`, find the maximum height on its left and right sides.
3. Calculate Trapped Water:
Determine the minimum height between the left and right boundaries.
Subtract the height of the current bar at index `i`.
Add the result to the total trapped water.
4. Return Result:
The total trapped water is the final result.
PYTHON CODE
def maxWater(arr, n):
res = 0
for i in range(1, n - 1):
left = arr[i]
for j in range(i):
left = max(left, arr[j])
right = arr[i]
for j in range(i + 1, n):
right = max(right, arr[j])
res += min(left, right) - arr[i]
return res
# Example usage:
arr = [1, 0, 2, 1, 0, 1]
n = len(arr)
print(maxWater(arr, n))
JAVA CODE
public class Main { res += [Link](left, right) - arr[i];
public static int maxWater(int[] arr, int n) }
{ return res;
for (int i = 1; i < n - 1; i++) { }
int left = arr[i]; public static void main(String[] args) {
for (int j = 0; j < i; j++) { int[] arr = { 1, 0, 2, 1, 0, 1};
left = [Link](left, arr[j]); int n = [Link];
} [Link](maxWater(arr, n));
int right = arr[i]; }
for (int j = i + 1; j < n; j++) { }
right = [Link](right, arr[j]);
}
SPIRAL MATRIX
Print a given matrix in spiral form.
Given a 2D array, print it in spiral form. Refer the following examples.
 Example 1:
Example 1:

Input: Input:
1 2 3 4 1 2 3 4 5 6
5 6 7 8 7 8 9 10 11 12
9 10 11 12 13 14 15 16 17 18
13 14 15 16
Output:
1 2 3 4 5 6 12 18 17 16 15 14
Output: 13 7 8 9 10 11
1 2 3 4 8 12 16 15 14 13 9 5 6
7 11 10
LOGIC
1. Initialization:
Initialize four variables: `k` for the starting row, `l` for the starting column, `m` for the ending
row, and `n` for the ending column.
2. Spiral Traversal:
While `k` is less than `m` and `l` is less than `n`, do the following:
Print the elements of the top row from index `l` to `n1`.
Increment `k`.
Print the elements of the rightmost column from index `k` to `m1`.
Decrement `n`.
If `k` is still less than `m`, print the elements of the bottom row from index `n1` to `l`.
Decrement `m`.
If `l` is still less than `n`, print the elements of the leftmost column from index `m1` to `k`.
Increment `l`.
3. Repeat Until Completion:
Repeat the above steps until all elements are printed.
This approach ensures that the matrix is traversed in a spiral manner, starting from the outer layer and
moving towards the center.
PYTHON CODE
def spiralPrint(a):
k, l, m, n = 0, 0, len(a), len(a[0])
while k < m and l < n:
for i in range(l, n):
print(a[k][i], end=" ")
k += 1
for i in range(k, m):
print(a[i][n - 1], end=" ")
n -= 1
if k < m:
for i in range(n - 1, l - 1, -1):
print(a[m - 1][i], end=" ")
m -= 1
if l < n:
for i in range(m - 1, k - 1, -1):
print(a[i][l], end=" ")
l += 1
matrix = [
[1, 2, 3, 4],
[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]
]
spiralPrint(matrix)
JAVA CODE
import [Link]; [Link](a[m - 1][i] + "
");
class Main { }
static void spiralPrint(int m, int m--;
n, int a[][]) { }
int i, k = 0, l = 0; if (l < n) {
while (k < m && l < n) { for (i = m - 1; i >= k; --i)
for (i = l; i < n; ++i) { {
[Link](a[k][i] + " [Link](a[i][l] +
"); " ");
} }
k++; l++;
for (i = k; i < m; ++i) { }
[Link](a[i][n - 1] }
+ " "); }
} public static void main(String[]
n--; args) {
if (k < m) { Scanner scanner = new
for (i = n - 1; i >= l; --i) Scanner([Link]);
{ [Link]("Enter the
number of rows: ");
int R = [Link]();
[Link]("Enter the number of columns: ");
int C = [Link]();
int a[][] = new int[R][C];
[Link]("Enter the matrix elements:");
for (int i = 0; i < R; i++) {
for (int j = 0; j < C; j++) {
a[i][j] = [Link]();
}
}
[Link]();
spiralPrint(R, C, a);
}
}
0-1 KNAPSACK ALGORITHM
You are given N items that cannot be broken. Each item has a weight and value

associated with it.

You also have a KnapSack of capacity W.

Find the maximum value of items you can collect in the KnapSack so that the total

weight does not exceed W.

Input Format:

First line contains the values N and W.

Second line contains N integers denoting the weights.

Last line contains N integers denoting the values.

Output Format

Print the maximum value that can be collected with total weight less than or equal

to W.
Example 1

Input

3 5

1 2 3

1 5 3

Output

Explanation

We can choose item number 2 and 3 to get the value as 5+3(8) and total weight as 5

which is less than or equal to W(5).

Example 2

Input

4 10

5 4 6 3

10 40 30 50

Output

90

Explanation

We can choose item number 2 and 4 to get the value as 40+50(90) and total weight as

7 which is less than or equal to W(10).

LOGIC
1. Prepare a Table:
Imagine a table where rows represent the items you can choose, and columns represent the capacity of
your knapsack.
2. Initialize the Table:
Start by filling the first row and first column with zeros, indicating that with no items or no
capacity, the value is zero.
3. Consider Each Item:
Go through each item one by one.
For each item, think about whether it's better to include it in the knapsack or not.
4. Decision Making:
If adding the current item doesn't exceed the capacity, compare the value of including it with the
value without it. Choose the maximum.
If adding the item exceeds the capacity, skip it.
5. Build Up the Table:
Keep going through all items and capacities, making decisions and updating the table.
6. Final Answer:
The value in the last cell of the table represents the maximum value you can achieve with the given
items and knapsack capacity.
7. Return the Result:
That final value is your answer – it's the maximum value you can get without overloading your
knapsack.
In essence, it's like deciding which items to pack into a knapsack of limited capacity to maximize the
total value.
PYTHON CODE
def knapSack(N, W, wt, val):
dp = [[-1 for _ in range(W + 1)] for _ in range(N + 1)]
def knapSackHelper(N, W):
if N == 0 or W == 0:
return 0
if dp[N][W] != -1:
return dp[N][W]
if wt[N - 1] <= W:
dp[N][W] = max(val[N - 1] + knapSackHelper(N - 1, W - wt[N -
1]),
knapSackHelper(N - 1, W))
return dp[N][W]
else:
dp[N][W] = knapSackHelper(N - 1, W)
return dp[N][W]
return knapSackHelper(N, W)
n, W = map(int, input().split())
weights = list(map(int, input().split()))
values = list(map(int, input().split()))
result = knapSack(n, W, weights, values)
print(result)
JAVA CODE
import [Link].*; return knapSack(N, W, wt, val, dp);
class solution }
{ }
static int knapSack(int N, int W, int[] public class Main {
wt, int[] val, int[][] dp) { public static void main(String[] args)
if (N == 0 || W == 0) {
return 0; Scanner sc = new
if (dp[N][W] != -1) Scanner([Link]);
return dp[N][W]; int n, W;
if (wt[N - 1] <= W) n = [Link]();
return dp[N][W] = W = [Link]();
[Link](val[N - 1] + knapSack(N - 1, W - int[] wt = new int[n];
wt[N - 1], wt, val, dp), int[] val = new int[n];
knapSack(N - 1, W, wt, val, for (int i = 0; i < n; i++)
dp)); wt[i] = [Link]();
return dp[N][W] = knapSack(N - 1, W, wt, for (int i = 0; i < n; i++)
val, dp); val[i] = [Link]();
} solution
public int knapSack(int N, int W, int[] Obj = new solution
wt, int[] val) { ();
int dp[][] = new int[N + 1][W + 1]; int result = [Link](n, W, wt,
for (int i = 0; i <= N; i++) { val);
for (int j = 0; j <= W; j++) { [Link](result);
dp[i][j] = -1; [Link]();
} }
} }
NUMBER OF LONGEST INCREASING
SUBSEQUENCES
A Longest Increasing Subsequence (LIS) is a subsequence of a given sequence of

numbers (not necessarily contiguous) in which the elements are in strictly

increasing order.

In other words, the Longest Increasing Subsequence problem asks for the length of

the longest subsequence such that all elements of the subsequence are sorted in

ascending order.
Consider the input sequence: [10, 22, 9, 33, 21, 50, 41, 60, 80]

The Longest Increasing Subsequence in this case is: [10, 22, 33, 50, 60, 80]
EXPLANATION

We start with the first element, 10, and consider it as the first element of a

potential increasing subsequence.

Move to the next element, 22. It's greater than 10, so we include it in the

potential subsequence.

Move to the next element, 9. It's less than 22, so we can't include it in the

current subsequence. We skip it.

Move to the next element, 33. It's greater than 22, so we include it in the

potential subsequence.
EXPLANATION

Move to the next element, 21. It's less than 33, so we skip it.

Move to the next element, 50. It's greater than 33, so we include it in the

potential subsequence.

Move to the next element, 41. It's less than 50, so we skip it.

Move to the next element, 60. It's greater than 50, so we include it in the

potential subsequence.

Move to the next element, 80. It's greater than 60, so we include it in the

potential subsequence.

The final Longest Increasing Subsequence is [10, 22, 33, 50, 60, 80] with a length

of 6.
LOGIC

1. Initialize:
Create an array `lis` of length `n` filled with 1s.
2. Dynamic Programming:
Iterate through each element in the array (index `i` from 1 to `n`).
For each element, compare it with previous elements.
If current element is greater than the previous one and can extend the LIS, update
`lis[i]`.
3. Result:
Return the maximum value in the `lis` array, representing the length of the Longest
Increasing Subsequence.
PYTHON CODE
def lis(arr, n):
lis = [1] * n
max_length = 0

for i in range(1, n):

for j in range(i):
if arr[i] > arr[j] and lis[i] < lis[j] + 1:
lis[i] = lis[j] + 1

for i in range(n):
max_length = max(max_length, lis[i])

return max_length

# Example usage:
arr = [10, 22, 33, 50, 60, 80]
n = len(arr)
print(lis(arr, n))
JAVA CODE
class Main { max = lis[i];
static int lis(int arr[], int n) return max;
{ }
int lis[] = new int[n]; public static void main(String
int i, j, max = 0; args[])
for (i = 0; i < n; i++) {
lis[i] = 1; int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60
for (i = 1; i < n; i++) };
for (j = 0; j < i; j++) int n = [Link];
if (arr[i] > arr[j] && lis[i] < lis[j] + 1) [Link](lis(arr, n));
lis[i] = lis[j] + 1; }
for (i = 0; i < n; i++) }
if (max <
lis[i])
WILDCARD PATTERN MATCHING
You are given a pattern string containing letters and wildcard characters. The wildcard
character * can match any sequence of characters (including an empty sequence), and the
wildcard character ? can match any single character. Your task is to implement a
function that determines whether a given input string matches the provided pattern.

Here are the rules for wildcard matching:

The wildcard character * can match any sequence of characters (including an empty
sequence).
The wildcard character ? can match any single character.
For example:
The pattern "h*t" matches strings like "hat," "hot," "hut," etc.
The pattern "c?t" matches strings like "cat," "cot," "cut," etc.
The pattern "ab*d" matches strings like "abd," "abcd," "abbd," etc.
Write a function isMatch(pattern: str, input_str: str) -> bool that returns True if the
input string matches the pattern, and False otherwise.
LOGIC

1. Initialize 2D Array:
Create a 2D array `T` of size `(n+1) x (m+1)`.

2. Base Case Initialization:

Set `T[0][0] = True`.
For each `j` from 1 to `m`, if pattern at `j1` is '*', set `T[0][j] = T[0][j1]`.

3. Fill 2D Array:
Iterate through each `i` and `j`.
If pattern at `j1` is '*', update `T[i][j] = T[i1][j] or T[i][j1]`.
If pattern at `j1` is '?' or matches word at `i1`, set `T[i][j] = T[i1][j1]`.

4. Result:
Return `T[n][m]`.
PYTHON CODE
def isMatch(word, pattern):
n = len(word)
m = len(pattern)
T = [[False] * (m + 1) for _ in range(n + 1)]
T[0][0] = True
for j in range(1, m + 1):
if pattern[j - 1] == '*':
T[0][j] = T[0][j - 1]
for i in range(1, n + 1):
for j in range(1, m + 1):
if pattern[j - 1] == '*':
T[i][j] = T[i - 1][j] or T[i][j - 1]
elif pattern[j - 1] == '?' or word[i - 1] ==
pattern[j - 1]:
T[i][j] = T[i - 1][j - 1]
return T[n][m]
# Example usage:
word = "xyxzzxy"
pattern = "x*****x?"
if isMatch(word, pattern):
print("Match")
else:
print("No Match")
JAVA CODE
public class Main { T[i][j] = T[i - 1][j - 1];
public static boolean isMatch(String word, }
String pattern) { }
int n = [Link](); }
int m = [Link](); return T[n][m];
boolean[][] T = new boolean[n + 1][m + 1]; }public static void main(String[] args) {
T[0][0] = true; String word = "xyxzzxy";
for (int j = 1; j <= m; j++) { String pattern = "x***x?";
if ([Link](j - 1) == '*') { if (isMatch(word, pattern)) {
T[0][j] = T[0][j - 1]; [Link]("Match");
} } else {
} [Link]("No Match");
for (int i = 1; i <= n; i++) { }
for (int j = 1; j <= m; j++) { }
if ([Link](j - 1) == '*') { }
T[i][j] = T[i - 1][j] || T[i][j - 1];
} else if ([Link](j - 1) == '?'
||
[Link](i - 1) ==
[Link](j - 1)) {
HOUSE ROBBER
You are a professional robber planning to rob houses along a street. Each house
has a certain amount of money stashed, the only constraint stopping you from
robbing each of them is that adjacent houses have security systems connected and
it will automatically contact the police if two adjacent houses were broken into
on the same night.
Given an integer array nums representing the amount of money of each house, return
the maximum amount of money you can rob tonight without alerting the police.
Test cases:

Explanation: Rob house 1 (money = 1) and then

Example 1:
rob house 3 (money = 3).
Input: nums = [1,2,3,1]
Total amount you can rob = 1 + 3 = 4.
Output: 4
Test cases:

Explanation: Rob house 1 (money = 2), rob

Example 2:
house 3 (money = 9) and rob house 5 (money =
Input: nums = [2,7,9,3,1]
1).
Output: 12
Total amount you can rob = 2 + 9 + 1 = 12.
LOGIC

1. Base Cases:
If no houses, no money can be robbed.
If only one house, rob the money in that house.
2. Dynamic Programming:
Create a list `dp` to store max robbed amounts.
3. Recurrence Relation:
To calculate max amount at each house, choose the maximum between:
Amount robbed without current house.
Amount robbed with the current house, plus the amount two houses ago.
4. Initialization:
Initialize first two values in `dp`.
5. Iterative Update:
Iterate through houses, updating `dp` based on the recurrence relation.
6. Result:
Result is the maximum amount in the `dp` list.
This method ensures choosing the best option at each house, either by skipping it or
considering it, to maximize the total amount robbed.
PYTHON CODE
class Solution:
def rob(self, nums):
n = len(nums)
if n == 0:
return 0
if n == 1:
return nums[0]
dp = [0] * n
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
solution = Solution()
nums1 = [1, 2, 3, 1]
print("Maximum amount you can rob:", [Link](nums1)) # Output: 4
nums2 = [2, 7, 9, 3, 1]
print("Maximum amount you can rob:", [Link](nums2)) # Output: 12
JAVA CODE
class Solution {
public int rob(int[] nums) {
final int n = [Link];
if (n == 0)
return 0;
if (n == 1)
return nums[0];
// dp[i] := max money of robbing nums[0..i]
int[] dp = new int[n];
dp[0] = nums[0];
dp[1] = [Link](nums[0], nums[1]);
for (int i = 2; i < n; ++i)
dp[i] = [Link](dp[i - 1], dp[i - 2] + nums[i]);
return dp[n - 1];
}
}
EDIT DISTANCE
Given two strings s1 and s2. Return the minimum number of operations
required to convert s1 to s2. The possible operations are permitted:

Insert a character at any position of the string.

Remove any character from the string.
Replace any character from the string with any other character.
Input Format
Input consists of two lines, strings s1 and s2
Output Format
Print the minimum number of operations required to convert s1 to s2.
Example 1
Input
horse
ros
Output
3
Explanation
horse -> rorse (replace 'h' with 'r')
rorse -> rose (remove 'r')
rose -> ros (remove 'e')
Example 2
Input
intention
execution
Output
5
Explanation
intention -> inention (remove 't')
inention -> enention (replace 'i' with 'e')
enention -> exention (replace 'n' with 'x')
exention -> exection (replace 'n' with 'c')
exection -> execution (insert 'u')
LOGIC
1. Initialization:
Create a 2D array `dp` with dimensions `(len(s1) + 1) x (len(s2) + 1)`.
Initialize the first row and column with indices, representing the cost of insertions and
removals.
2. Dynamic Programming:
Iterate through characters in both strings.
If characters are equal, `dp[i][j] = dp[i1][j1]`.
If characters are different, `dp[i][j] = 1 + min(dp[i][j1], dp[i1][j], dp[i1][j1])`.
3. Return Result:
Return `dp[len(s1)][len(s2)]`.
This simplified version retains the essence of the logic, focusing on the minimum operations for
insertion, removal, or replacement.
PYTHON CODE
def edit_distance(s1, s2):
dp = [[-1 for _ in range(len(s2) + 1)] for _ in range(len(s1) + 1)]
return rec(s1, s2, len(s1), len(s2), dp)
def rec(s, t, x, y, dp):
if x == 0:
return y
if y == 0:
return x
if dp[x][y] != -1:
return dp[x][y]
if s[x - 1] == t[y - 1]:
dp[x][y] = rec(s, t, x - 1, y - 1, dp)
else:
dp[x][y] = min(
1 + rec(s, t, x, y - 1, dp),
min(1 + rec(s, t, x - 1, y, dp), 1 + rec(s, t, x - 1, y - 1, dp))
)
return dp[x][y]
s1 = input()
s2 = input()
print(edit_distance(s1, s2))
JAVA CODE
import [Link].*; public static int rec(String s, String t,
public class Main { int x, int y) {
public static void main(String[] args) { if (x == 0) return y;
Scanner sc = new Scanner([Link]); if (y == 0) return x;
String s1 = [Link](), s2 = [Link](); if (dp[x][y] != -1) return dp[x][y];
[Link](); if ([Link](x - 1) == [Link](y - 1))
[Link](editDistance(s1, dp[x][y] =
s2)); rec(s, t, x - 1, y - 1); else dp[x]
} [y] =
static int[][] dp; [Link](
public static int editDistance(String s1, 1 + rec(s, t, x, y - 1),
String s2) { [Link](1 + rec(s, t, x - 1, y), 1
dp = new int[[Link]() + 1] + rec(s, t, x - 1, y - 1))
[[Link]() + 1]; );
for (int[] d : dp) [Link](d, -1); return dp[x][y];
return rec(s1, s2, [Link](), }
[Link]()); }
}