Indira Gandhi Delhi Technical University

for Women
(established by the Govt. NCT of Delhi vide Delhi Act 09 of 2012)
(Formerly Indira Gandhi Institute of Technology)
Kashmiri Gate, Delhi – 110006

DFS Practical File

Submitted to:
Dr. Shweta Jindal
IT Department

Submitted By:
Sapna Morya
05604092025
MCA (Sem-1)
 DFS Practical File Dec’25

1. Two Sum
Given an array of integers nums and an integer target, return indices of the two numbers
such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the
same element twice.
Code: class Solution {

public int[] twoSum(int[] nums, int target) {

int n = [Link];

for (int i = 0; i < n; i++) {

for(int j = i + 1; j < n; j++) {

if (nums[i] + nums[j] == target) {

return new int[]{i, j};}

}}

return new int[0];}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

9. Palindrome Number
Given an integer x, return true if x is a palindrome, and false otherwise.
Code: class Solution {
public boolean isPalindrome(int x) {
int reverse = 0;
int temp = x;
while (temp!=0){
reverse = (reverse*10)+ temp%10;
temp = temp/10;
}
if (reverse==x && x>=0){
return(true);
} else{
return(false);}
}}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

13. Roman to Integer

Roman numerals are usually written largest to smallest from left to right. However, the
numeral for four is not IIII. Instead, the number four is written as IV. Because the one is
before the five we subtract it making four. The same principle applies to the number nine,
which is written as IX. There are six instances where subtraction is used:
 I can be placed before V (5) and X (10) to make 4 and 9.
 X can be placed before L (50) and C (100) to make 40 and 90.
 C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer.
Code: class Solution {
public int getValue(char c) {
if (c == 'I') return 1;
if (c == 'V') return 5;
if (c == 'X') return 10;
if (c == 'L') return 50;
if (c == 'C') return 100;
if (c == 'D') return 500;
if (c == 'M') return 1000;
return 0;
}
public int romanToInt(String s) {
int integer=0;
for(int i=0;i<[Link]()-1;i++){
char ch1 = [Link](i);
char ch2 = [Link](i+1);
if(getValue(ch1)<getValue(ch2)){
integer-=getValue(ch1);}
else{
integer+=getValue(ch1);}
}
integer+=getValue([Link]([Link]()-1));
return integer;}}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

20. Valid Parenthesis

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input
string is valid.
An input string is valid if:
1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.
3. Every close bracket has a corresponding open bracket of the same type
Code: class Solution {
public boolean isValid(String s) {
Stack<Character> stack = new Stack<> ();
if ([Link]()){
return false;}
for (int i =0; i<[Link](); i++){
char c = [Link](i);
if (c=='(' || c=='{' || c=='['){

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

[Link](c);}
else{
if([Link]()){
return false; }
char top= [Link]();
if(c==')' && top!='(' || c=='}' && top!='{' || c==']' && top!='['){ return false;} }}
return [Link]();}}

21. Merge Two Sorted lists

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the
nodes of the first two lists.
Return the head of the merged linked list.
Code: lass Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* temp = new ListNode();
ListNode* tail = temp;

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

while (list1 != nullptr && list2 != nullptr) {

if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;}
else {tail->next = list2;
list2 = list2->next;}
tail = tail->next; }
if (list1 != nullptr) {
tail->next = list1; }
else {tail->next = list2; }
return temp->next; } };

26. Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-
place such that each unique element appears only once. The relative order of the elements
should be kept the same.

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

Consider the number of unique elements in nums to be k. After removing duplicates, return
the number of unique elements k.
The first k elements of nums should contain the unique numbers in sorted order. The
remaining elements beyond index k - 1 can be ignored.
Code: class Solution {
public int removeDuplicates(int[] nums) {
int count=1;
int j= nums[0];
int k=1;
for(int i=1;i<[Link];i++){
if(nums[i]!=j){
count+=1;
j=nums[i];
nums[k]=j;
k+=1; }}
return(count); }}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

27. Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-
place. The order of the elements may be changed. Then return the number of elements
in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted,
you need to do the following things:
 Change the array nums such that the first k elements of nums contain the elements
which are not equal to val. The remaining elements of nums are not important as
well as the size of nums.
 Return k.
Code: class Solution {

public int removeElement(int[] nums, int val) {

int index=0;
for(int i=0;i<[Link];i++){
if (nums[i]!= val){
nums[index] = nums[i];
index += 1; }}
return index;}}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

28. Find the index of the first occurrence in a String.

Given two strings needle and haystack, return the index of the first occurrence
of needle in haystack, or -1 if needle is not part of haystack.
Code: class Solution {
public int strStr(String haystack, String needle) {
if ([Link]() == 0) {
return 0; }
for (int i = 0; i <= [Link]() - [Link](); i++) {
int j = 0;
while (j < [Link]() && [Link](i + j) == [Link](j)) {
j++;}
if (j == [Link]()) {
return i; }
}
return -1; }
}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

35. Search insert position

Given a sorted array of distinct integers and a target value, return the index if the target is
found. If not, return the index where it would be if it were inserted in order.
You must write an algorithm with O(log n) runtime complexity.
Code: class Solution {
public int searchInsert(int[] nums, int target) {
int low=0;
int high= [Link]-1;
int mid;
while(low<=high){
mid= (low+high)/2;
if(nums[mid] == target){
return mid; }
if(nums[mid]<target){
low=mid+1; }
if(nums[mid]>target){
high=mid-1; }}
return low; }}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

58. Length of last word

Given a string s consisting of words and spaces, return the length of the last word in the
string.
A word is a maximal substring consisting of non-space characters only.
Code:
class Solution {
public int lengthOfLastWord(String s) {
int flag=0;
int count=0;
for(int i=[Link]() -1 ;i>=0;i--){
if([Link]([Link](i))){
flag=1;
count+=1; }
else{
if(flag==1){ return count; }
else{flag=0; }}}
return count; }}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

[Link] one
You are given a large integer represented as an integer array digits, where each digits[i] is
the ith digit of the integer. The digits are ordered from most significant to least significant in
left-to-right order. The large integer does not contain any leading 0's.
Increment the large integer by one and return the resulting array of digits.
Code: class Solution {
public int[] plusOne(int[] digits) {
int carry=1;
int last = [Link]-1;
for(int i= last; i>=0; i--){
if(digits[i]+1==10 && carry ==1){
digits[i]=0;
carry = 1; }
else{digits[i]=digits[i]+carry;
carry=0; }}
if(digits[0]==0){
int[] newDigits= new int[last +2];
for(int i= last; i>=0; i--){
newDigits[i+1] = digits[i]; }
newDigits[0]=1;
return newDigits; }
return digits; }}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

67. Add Binary

Given two binary strings a and b, return their sum as a binary string.
Code: class Solution {
public String addBinary(String a, String b) {
StringBuilder result = new StringBuilder();
int i = [Link]() - 1;
int j = [Link]() - 1;
int carry = 0;
while (i >= 0 || j >= 0 || carry != 0) {
int bit1 = 0;
int bit2 = 0;
if (i >= 0) {
bit1 = [Link](i) - '0';
i--;}
if (j >= 0) {
bit2 = [Link](j) - '0';
j--;}
int sum = bit1 + bit2 + carry;
[Link](sum % 2);
carry = sum / 2; }
return [Link]().toString();}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

69. Sqrt(x)
Given a non-negative integer x, return the square root of x rounded down to the nearest
integer. The returned integer should be non-negative as well.
You must not use any built-in exponent function or operator.
 For example, do not use pow(x, 0.5) in c++ or x ** 0.5 in python.
Code: class Solution {
public int mySqrt(int x) {
if(x==0 || x==1){
return x; }
int low=1;
int high=x/2;
int mid=0;
while(low<=high){
mid = low + (high-low)/2;
if((long)mid*mid==x){
return mid; }
else if((long)mid*mid>x){
high=mid-1; }
else{low=mid+1; }}
return low-1; }}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

70. Climbing Stairs

You are climbing a staircase. It takes n steps to reach the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the
top?
Code:
class Solution {
public int climbStairs(int n) {
int step1=0;
int step2=1;
int ans=0;
for(int i=1;i<=n;i++){
ans=step1+step2;
step1=step2;
step2=ans; }
return ans;}}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

83. Remove duplicate from sorted list

Given the head of a sorted linked list, delete all duplicates such that each element appears
only once. Return the linked list sorted as well.
Code: class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == nullptr) {
return head; }
ListNode* temp = head;
while (temp != nullptr && temp->next != nullptr) {
if (temp->val == temp->next->val) {
temp->next = temp->next->next;
} else {
temp = temp->next; }}
return head; }
};

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

88. Merge sorted array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and
two integers m and n, representing the number of elements
in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside
the array nums1. To accommodate this, nums1 has a length of m + n, where the
first m elements denote the elements that should be merged, and the last n elements are
set to 0 and should be ignored. nums2 has a length of n.
Code:
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1;
int j = n - 1;
int k = m + n - 1;
while (i >= 0 && j >= 0) {
if (nums1[i] > nums2[j]) {
nums1[k] = nums1[i];
i--;
}
else {
nums1[k] = nums2[j];
j--;}
k--;
}
while (j >= 0) {
nums1[k] = nums2[j];
j--;
k--;
}
}
}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

111. Minimum Depth of Binary Tree

Given a binary tree, find its minimum depth.
The minimum depth is the number of nodes along the shortest path from the root node
down to the nearest leaf node.
Note: A leaf is a node with no children.
Code: class Solution {
public int minDepth(TreeNode root) {
if (root == null) {
return 0; }
if ([Link] == null && [Link] == null) {
return 1; }
int leftDepth = Integer.MAX_VALUE;
int rightDepth = Integer.MAX_VALUE;
if ([Link] != null) {
leftDepth = minDepth([Link]);
}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

if ([Link] != null) {
rightDepth = minDepth([Link]);
}
return [Link](leftDepth, rightDepth) + 1;
}
}

169. Majority Element

Given an array nums of size n, return the majority element.
The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume
that the majority element always exists in the array.
Code:
class Solution {
public int majorityElement(int[] nums) {
int count = 0;
int candidate = 0;

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

for (int num : nums) {

if (count == 0) {
candidate = num;
}
if (num == candidate) {
count++;
} else {
count--;
}
}
return candidate;
}
}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

171. Excel Sheet Column Number

Given a string columnTitle that represents the column title as appears in an Excel sheet,
return its corresponding column number.
Code:
class Solution {
public int titleToNumber(String columnTitle) {
int result = 0;
for (int i = 0; i < [Link](); i++) {
char c = [Link](i);
int value = c - 'A' + 1;
result = result * 26 + value;
}
return result;
}
}

Sapna Morya 05604092025 MCA

 DFS Practical File Dec’25

540. Single Element in a Sorted Array

You are given a sorted array consisting of only integers where every element appears exactly
twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space
Code: class Solution {
public int singleNonDuplicate(int[] nums) {
int low = 0;
int high = [Link] - 1;
while (low < high) {
int mid = (low + high) / 2;
if (mid % 2 == 1) {
mid--; }
if (nums[mid] == nums[mid + 1]) {low = mid + 2; }
else {high = mid; }}
return nums[low]; }}

Sapna Morya 05604092025 MCA