DATA STRUCTURE

--------------------------------------------------------------------------------
Time Complexity
 Time complexity can NOT be defined as actual time taken by the program. Actual running time depends on many external factors:
 Hardware speed (old vs new machine)
 CPU architecture
 Memory and cache
 Compiler optimizations
 Programming language implementation
 Operating system load
Because of these variables, the same program may run 1 second on a fast machine, and 5 seconds on a slower machine. So,
measuring real time in seconds is unreliable for algorithm analysis.
 Time Complexity measures how the number of operations grows as input size increases. It focuses on growth of operations relative
to input size (n).
 Operations grow proportional to n, so the time complexity is O(n). This means if input doubles, operations roughly double.

 It’s expressed in Big O Notation (O) to show the upper bound of growth rate — i.e., worst-case scenario.
 Common Time Complexities

Example for Exponential is possible outcomes of tossing n coins.

 Types of Time Complexity Analysis

In interviews, worst-case is usually expected.

 You want to print numbers from 1 to N — for example, 1 2 3 4 5. You can do it in: Iterative way (using forr loop) and Recursive
way(using function calls).
◦ Both will execute N operations → so Time Complexity = O(N) for both. But the Space Complexity and performed behavior file.
 Why Iteration is Faster?
 Even though both perform the same number of logical operations, recursion does extra work internally:
 Saves local variables and return addresses on the stack.
 Jumps between functions (context switching).
 Java does not perform tail recursion optimization (unlike some languages like Python or Scala).
 Iteration (for loop) is generally preferred for simple tasks like printing 1 to N — it’s faster, more memory-efficient, and
safer. Recursion is elegant and sometimes necessary (like tree traversal, divide and conquer), but for linear sequences,
iteration wins in performance.
 Example for each time complexity
Space Complexity
 Space Complexity measures how much extra memory your program uses while running-apart from the space needed for the input itself.
 It’s the ‘memory cost’ of your algorithm.
 Imagine you have two containers filled with black chickpeas and white chickpeas. You need to exchange them (swap black and white).
 Without extra container
 You try to swap chickpeas directly between the two containers: You pick one chickpea from container A and one from
container B. But where do you temporarily keep one chickpea while you swap? You might have to hold it in your hand, which
is limited — the process becomes slow and messy.
 you use only a constant amount of extra space (your hand). It’s efficient in space, but sometimes hard to manage.
 With an extra container
 Now, you bring a third empty container.
 Pour all black chickpeas (A) into the new container. Move white chickpeas (B) into A. Move black chickpeas from the extra
container into B.
 Now, swapping becomes clean, easy, and safe, but you had to use one extra container — that’s extra space! This is like using
O(n) extra space
Hash Table and Map

 Before solving particular problem I advice to think about two questions for a few minutes:
bool answer = is it possible to apply HASH TABLE or MAP ?;
if(answer == true){
//Think: HOW YOU CAN APPLY ?
}
Helps in finding fast and easy solution for a problem.

 HASH TABLE and MAP are the types of containers which store data with key-value combination. It means that particular data will
have an special key and the value associated (mapped value) with this key.
<key, value>
For solving most of the problems knowing <key, value> combiantion is really enough.

 In C++, the unordered_map<> is used to implement a hash table, while map<> is implemented as a balanced binary search tree.

 In Java, their equivalents are:

◦ HashMap<K, V> → like C++’s unordered_map<>
◦ TreeMap<K, V> → like C++’s map<>
Both store key–value pairs and work on almost the same principle, but the main difference is:

So, if you need the keys to be sorted, use TreeMap. If you just need fast access and insertion, use HashMap.

 Creating Key-Value pairs

 You can use various type combinations:

◦ HashMap<Integer, Integer> q1 = new HashMap<>();
Stores simple key–value pairs (e.g., rollNo → marks).
 ◦ HashMap<Integer, List<Integer>> q2 = new HashMap<>();
Each key stores multiple values (e.g., studentId → list of scores).

◦ HashMap<Integer, List<List<String>>> q3 = new HashMap<>();

Each key stores a list of lists (e.g., courseId → list of batches → list of student names).
 ◦ HashMap<Character, [Link]<Integer, Character>> q4 = new HashMap<>();
Each key stores a pair (Integer, Character) — think of it like key → (count, nextCharacter).

◦ HashMap<String, Integer> q5 = new HashMap<>();

Maps string keys to numeric values (e.g., word → frequency).

 Methods for HashMap

Methods Use Example
put(key, value) Adds or updates key-value pair

get(key) Returns value for the given key

getOrDefault(key, defaultValue) Returns default value if key not

found
constainsKey(key) Checks if key exists
containsValue(value) Checks if any key maps to this
value
clear() Removes all entries/mapping

clone() Returns shallow copy of

HashMap instance; keys and
values are not cloned
isEmpty() Checks if map has no entries

size() Returns number of key-value

pairs

remove(key) Deletes entry by key

remove(key, value) Deletes only if both match

putIfAbsent(key, value) Adds only if key not present

replace(key, value) Updates value only if key exists

replace(key, oldValue, newValue) Updates only if current value

matches

replaceAll(function) Applies a function to all entries

forEach(action) Loops through all entries easily

keySet() Returns set of all keys

values() Returns collection of all values

entrySet() Returns all key-value pairs as Set

compute(key, function) Recalculate value for a key

computeIfAbsent(key, function) Computes and adds if key not

present

computeIfPresent(key, function) Updates only if key already exists

merge(key, value, function) If key exists – merges value, else

inserts new
Pattern Printing

Star Pattern 1

Logic:
 As the pattern contains equal number of rows and columns, so we need to take the input for row only, that can be used for column also.
 As we need to only print stars, simply iterate through each row and column, and print star there, using nested for loops.
TC: O(N²), since we print N stars for each of the N rows.
SC: O(1), no additional space is used apart from loop variables.

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

for(int j=1; j<=row; j++) {
[Link]("*");
}
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Star Pattern 2

Logic:
 Take an input for row.
 Iterate through each row using outer for loop, and print stars as the current row index.
TC: O(N²), since we print N stars for each of the N rows.
SC: O(1), no additional space is used apart from loop variables.

for(int i=1; i<=size; i++) {

for(int j=1; j<=row; j++) {
[Link]("*");
}
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Star Pattern 3

Algorithm:
 Take an input size.
 To iterate through the row: 1 to size.
 To iterate through column: for blank spaces (size-row), and for stars (=row)
TC: O(N²)
SC: O(1), no additional space is used apart from loop variables.
for(int i=1; i<=size; i++) {
for(int j=size-i; j>=1; j--) {
[Link](" ");
 }
for(int j=1; j<=i; j++) {
[Link]("*");
}
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Floyd’s Triangle

1
23
456
7 8 9 10

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
int count=1; // extra variable for counter

for(int i=1; i<=row; i++) {

for(int j=1 ; j<=i; j++) {
[Link](count++ +" "); // ‘count+++’ will do the same work
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Binary Triangle

1
01
101
0101

Logic 1: If you look at the 0’s position in a triangle formation, you will find out that the indexes i and j are either (even,odd) or (odd,even), but
not (odd,odd) or (even,even).
(1,1)
(2,1) (2.2)
(3,1) (3,2) (3,3)
(4,1) (4,2) (4,3) (4,4)

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=i; j++) {
if((i%2==0 && j%2!=0)||(i%2!=0 && j%2==0)) {
[Link]("0 ");
} else [Link]("1 ");
}
[Link]();
}
}
}

Logic 2: If you look at position of 0’s and 1’s you will find out that the (i+j) of 1’s are even, whereas (i+j) of 0’s are odd.
1
01
101
0101
10101
(1,1)
(2,1) (2.2)
(3,1) (3,2) (3,3)
(4,1) (4,2) (4,3) (4,4)
(5,1) (5,2) (5,3) (5,4) (5,5)

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=i; j++) {
if((i+j)%2!=0) {
[Link]("0 ");
} else [Link]("1 ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Odd Number Triangle

1
13
135
1357

Logic 1: As we can see, on each row we have a series of odd numbers starting from 1. Here, we are going to use an extra variable ‘odd’ to start
the odd number from 1, and then we are going to increment odd number by 2, at each step.

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
int odd = 1;
for(int j=1 ; j<=i; j++) {
[Link](odd+" ");
odd+=2;
}
[Link]();
}
}
}

Logic 2:
public class PatternPrinting {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=i; j++) {
[Link](2*j-1+" ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Odd Number Triangle

*
**
***
****

Logic 1: One iteration should be done for row,

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row-i; j++) {
[Link](" ");
}
for(int j=1; j<=i; j++) {
[Link]("* ");
}
[Link]();
}
}
}

Logic 2:
1234
1 *
2 **
3 ***
4****

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row; j++) {
if((i+j)>row) [Link]("* ");
else [Link](" ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Number Triangle Vertically Flipped

1
12
123
1234

Logic 1:

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row-i; j++) {
[Link](" ");
}
for(int j=1 ; j<=i; j++) {
[Link](j+" ");
}
[Link]();
}
}
}

Logic 2:
public class PatternPrinting {
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row; j++) {
if((i+j)>row) [Link](j+" ");
else [Link](" ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Alphabet Triangle Vertically Flipped

A
BB
CCC
DDDD

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row-i; j++) {
[Link](" ");
}
for(int j=1 ; j<=i; j++) {
[Link]((char)(i+64)+" ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Rhombus

****
****
****
****

Logic 1:
****
****
****
****

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row-i; j++) {
[Link](" ");
}
for(int j=1 ; j<=i; j++) {
[Link]("* ");
}
for(int j=1; j<=row-i; j++) {
[Link]("* ");
}
 [Link]();
}
}
}

Logic 2:
* * * * → 3 spaces & 4 stars
* * * * → 2 spaces & 4 stars
* * * * → 1 space & 4 stars
* * * * → 0 space & 4 stars

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row-i; j++) {
[Link](" ");
}
for(int j=1 ; j<=row; j++) {
[Link]("* ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Double Flipped Triangle

****
***
**
*

Logic 1:
* * * * → 0 spaces 4 stars
* * * → 1 spaces 3 stars
* * → 2 spaces 2 stars
* → 3 spaces 1 stars

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=i-1; j++) {
[Link](" ");
}
for(int j=1 ; j<=row-i+1; j++) {
[Link]("* ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Pyramid

*
***
*****
*******

Logic 1:
* → 3 spaces 1 stars
 * * * → 2 spaces 3 stars
* * * * * → 1 spaces 5 stars
* * * * * * * → 0 spaces 7 stars

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1 ; j<=row-i; j++) {
[Link](" ");
}
for(int j=1 ; j<=2*i-1; j++) {
[Link]("* ");
}
[Link]();
}
}
}

Logic 2: Put star only to that position where (i+j)>row index.

1234567
1 * → (1+4) > row
2 * * * → (2+3) > row
3 * * * * * → (3+2) > row
4 * * * * * * * → (4+1) > row

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
for(int i=1; i<=row; i++) {
for(int j=1; j<=row+i-1; j++) {
if((i+j)>row) [Link]("* ");
else [Link](" ");
}
[Link]();
}
}
}

Logic 3 (Track of spaces and stars):

At starting, nsp=row-1, and nst=1
Then as we move to next position, we are going to decerement spaces by 1 (ie., nsp-=1), and incerement the stars by 2 (ie., nst+=2).

1234567
1 * → 3 spaces 1 star
2 * * * → 2 spaces 3 star
3 * * * * * → 1 space 5 star
4 * * * * * * * → 0 space 7 star

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
int nsp = row-1; // number of spaces
int nst = 1; // number of stars
for(int i=1; i<=row; i++) {
for(int j=1; j<=nsp; j++) {
[Link](" ");
}
for(int j=1; j<=nst; j++) {
[Link]("* ");
}
nsp--;
nst+=2;
[Link]();
}
 }
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Number Pyramid

1
123
12345
1234567

Logic:

public class PatternPrinting {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
int nsp = row-1; // number of spaces
int nst = 1; // number of stars
for(int i=1; i<=row; i++) {
for(int j=1; j<=nsp; j++) {
[Link](" ");
}
for(int j=1; j<=nst; j++) {
[Link](j+" ");
}
nsp--;
nst+=2;
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Diamond

*
***
*****
*******
*****
***
*

Logic:
 Diamond is printed in two halves.
 First half: spaces decrease, stars increase by 2.
 Second half: spaces increase, stars decrease by 2.
 Before second half, you need to set the nsp and nst as per the second half initial row.

4 rows
3 spaces 1 star
*
23
***
15
*****
07
*******
-1 9
0 7 (eliminate this)
*******
15
*****
23
***
31
*

4
31
*
23
***
15
*****
07
*******
15
*****
23
***
31
*

public class Diamond {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();
int nsp = 3;
int nst = 1;
for(int i=1; i<=row; i++) {
[Link](nsp+" "+nst);
for(int j=1; j<=nsp; j++) {
[Link](" ");
}
for(int j=1; j<=nst; j++) {
[Link]("* ");
}
nsp--;
nst+=2;
[Link]();
}
[Link]();
// [Link](nsp+" "+nst); //-1 9
nsp++;
nst-=2;
for(int i=1; i<=row-1; i++) {
nsp++;
nst-=2;
[Link](nsp+" "+nst); // 1 5 for j=1
for(int j=1; j<=nsp; j++) {
[Link](" ");
}
for(int j=1; j<=nst; j++) {
[Link]("* ");
}

[Link]();
}
}
}

Logic 2:
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Bridge

*********
**** ****
*** ***
** **
* *

Logic:
 The above pattern displayed for row=5.
 To display the following code, we first make a separate for loop for the 1st row.

*********
**** ****
*** ***
** **
* *

****_****
***___***
**_____**
*_______*

package Pattern_Printing;

import [Link];

public class Bridge {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();

for(int i=1; i<=2*row-1; i++) {

[Link]("* ");
}
[Link]();
for(int i=1; i<=row-1; i++) {
for(int j=1; j<=row-i; j++) {
[Link]("* ");
}
for(int j=1; j<=2*i-1; j++) {
[Link](" ");
}
for(int j=1; j<=row-i; j++) {
[Link]("* ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Iterate an row with outer loop
 Iterate inner loop till (TotalRow + 1) - i.
 Print star.
 Iterate two separate inner loops for spaces.
 Iterate one more inner loop for other side of star.

 Same way, do it for another outer loop for other side.

 While printing stars, you need to range it from 1 to i.
 And for printing spaces, you need to start from 1 till (TotalRow-i).

for(int i=1; i<=row; i++) {

for(int j=1; j<=(row+1)-i; j++) {
[Link]("*");
}
for(int j=1; j<=i-1; j++) {
[Link](" ");
}
for(int j=1; j<=i-1; j++) {
[Link](" ");
}
for(int j=1; j<=(row+1-i); j++) {
[Link]("*");
}
[Link]();
}
for(int i=1; i<=row; i++) {
for(int j=1; j<=i; j++) {
[Link]("*");
}
for(int j=1; j<=row-i; j++) {
[Link](" ");
}
for(int j=1; j<=row-i; j++) {
[Link](" ");
}
for(int j=1; j<=i; j++) {
[Link]("*");
}
 [Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Symmetric Butterfly Pattern

Logic:
 Looking at the total row count (ie., N) and the figure. It is clearly visible that we need to perform two separate outer loop. First part would
contain first 5 rows and next half would contain next 4 rows (or remaining rows).
 For the first half, we need to divide it into 4 parts. One part would contain stars , other two part would contain spaces, and last part
would contain stars.
 Based on the number of stars and spaces, iterate the inner loop till that index.

for(int i=1; i<=row; i++) {

for(int j=1; j<=i; j++) {
[Link]("*");
}
for(int j=1; j<=row-i; j++) {
[Link]("_");
}
for(int j=1; j<=row-i; j++) {
[Link]("_");
}
for(int j=1; j<=i; j++) {
[Link]("*");
}
[Link]();
}
for(int i=1; i<=row-1; i++) {
for(int j=1; j<=row-i; j++) {
[Link]("*");
}
for(int j=1; j<=i; j++) {
[Link]("_");
}
for(int j=1; j<=i; j++) {
[Link]("_");
}
for(int j=1; j<=row-i; j++) {
[Link]("*");
 }
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Hollow Rectangle Pattern

Logic:
 It is visible that they have not iterated till 5th index, but one less than 5.
 As this figure can be seen as unique pattern, so need to look at its stars position, in order to get an idea of solving approach.
(1,1) (1,2) (1,3) (1,4)
(2,1) (2,4)
(3,1) (3,4)
(4,1) (4,2) (4,3) (4,4)
 We can clearly that the position of stars must have either 1 or 4 at outer or inner index.

for(int i=1; i<row; i++) {

for(int j=1; j<row; j++) {
if(i==1 || j==1 || i==4 || j==4) {
[Link]("*");
} else {
[Link](" ");
}
}
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1___ ___1
12__ __21
123_ _321
1234 4321

Logic:
 Iterate outer loop through row.
 Iterate inner loop for numbers as per row count.
 Print column values (or loop values).
 Iterate inner loop for spaces as (TotalRow - CurrentRow).
 Iterate inner loop for spaces as (TotalRow - CurrentRow).
  Iterate inner loop for numbers as reverse number from row count to 1.
 Print loop values.

for(int i=1; i<=row; i++) {

for(int j=1; j<=i; j++){
[Link](j);
}
for(int j=1; j<=row-i; j++) {
[Link](" ");
}
for(int j=1; j<=row-i; j++) {
[Link]("_");
}
for(int j=i; j>=1; j--) {
[Link](j);
}
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Logic:
 Iterate through row.
 While iterating column: consider the current row.
 Initialize num variable with 1.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

→ if(i<j) [Link](i+" ");

else [Link](j+" ");

1 2 3 4 5 6 7 → ith index
1→ 1111
2 1222
3 1233
4 1234
for(int i=1; i<=row; i++) {
for(int j=1; j<=row; j++) {
[Link]([Link](i,j)+" ");
// [Link](((i<j) ? i : j)+" "); // Ternary operation
// if(i<j) [Link](i+" ");
// else [Link](j+" ");
}
[Link]();
}
 5 6 7 → actual jth index
3 2 1 → fake jth index (in reverse order)
1 111
2 221
3 321
4 321
// Concept of fake values
for(int i=1; i<=row; i++) {
for(int j=row-1; j>=1; j--) { //this will treat 5th, 6th, and 7th column indexes as 1st, 2nd, and 3rd
[Link]([Link](i,j)+" ");
}
[Link]();
}

1 2 3 4 5 6 7 → actual index
1 2 3 3 2 1 → jth index
53→ 1233321
62 1222221
71 1111111
for(int i=row-1; i>=1; i--) {
for(int j=1; j<=row-1; j++) {
[Link]([Link](i,j)+" ");
}
for(int j=1;j<=1; j++) {
[Link](i+" ");
}
for(int j=row-1; j>=1; j--) {
[Link]([Link](i,j)+" ");
}
[Link]();
}

public class NumberSpiral {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int row = [Link]();

for(int i=1; i<=row; i++) {

for(int j=1; j<=row; j++) {
[Link]([Link](i,j)+" ");
// [Link](((i<j) ? i : j)+" "); // Ternary operation
// if(i<j) [Link](i+" ");
// else [Link](j+" ");
}
for(int j=row-1; j>=1; j--) { //this will treat 5th, 6th, and 7th column indexes as 1st, 2nd, and 3rd
[Link]([Link](i,j)+" ");
}
[Link]();
}
for(int i=row-1; i>=1; i--) {
for(int j=1; j<=row-1; j++) {
[Link]([Link](i,j)+" ");
}
for(int j=1;j<=1; j++) {
[Link](i+" ");
}
for(int j=row-1; j>=1; j--) {
[Link]([Link](i,j)+" ");
}
[Link]();
}
}
}

Logic 2:

public class NumberSpiral {

public static void main(String[] args) {
 Scanner sc = new Scanner([Link]);
int row = [Link]();

for(int i=1; i<=2*row-1; i++) {

for(int j=1; j<=2*row-1; j++) {
int a=i, b=j;
if(i>row) a=2*row-i;
if(j>row) b=2*row-j;
[Link]([Link](a,b)+" ");
}
[Link]();
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Number Illusion Pattern

Logic:
 If we look at this first part, we can see the number is in decreasing order, which indicates that we need to use indexing in reverse order.

 In first part we can see one pattern, while comparing row with column, the larger index number would get printed.

 If we look at the second part , we can see the number is now in increasing order, we just need to find the order of index for both row and
column. [the idea of finding the index number for both row and column. Check the maximum occurring number in that line.] [Here, index
for outer loop would remain same. As it is of the same row.]

 For the remaining part, the column index would remain same, we just need to find the order of both part of remaining part. [No change
in column. And for row, think of the maximum occurring number in that line.]

 The third part or the first part of remaining part, the index of row would be based on logic that the maximum occurring number in that
line.
 The fourth part row index, would be based on same logic. Max occurring number would be the row index, and the larger value comparing
row and column would get printed.

for(int i=row; i>=1; i--) {

for(int j=row; j>=1; j--) {
if(i>j) {
[Link](i);
} else {
[Link](j);
}
}
for(int j=2; j<=row; j++) {
if(i>j) {
[Link](i);
} else {
[Link](j);
}
}
[Link]();
}
for(int i=2; i<=row; i++) {
for(int j=row; j>=1; j--) {
if(i>j) {
[Link](i);
} else {
[Link](j);
}
}
for(int j=2; j<=row; j++) {
if(i>j) {
[Link](i);
} else {
[Link](j);
}
}
[Link]();
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Java Collections
 Java Collections Framework (JCF): The JCF is part of the [Link] package and provides a set of ready-to-use classes and interfaces for
storing and manipulating groups of objects. Collections are dynamic — meaning they can grow or shrink in size and they come with built-
in methods for common operations.

 The Java Collections Framework isn’t just a random set of classes it’s an organized hierarchy. At the top sits the Iterable interface, which
allows objects to be looped through using the enhanced for-each loop. Then comes the Collection interface, which represents a group
of elements and defines basic operations like adding, removing, checking size, and clearing elements.
 From Collection, the hierarchy splits into three main branches:
 List : ordered collections that can have duplicate elements.
 Set : unordered collections that do not allow duplicates.
 Queue : collections designed to hold elements before processing.
 Alongside these is the Map interface, which isn’t technically a subtype of Collection but is still part of the framework. A Map
stores data in key-value pairs, ensuring that each key is unique.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Basic maths

Count all digits of a number

Logic:
 Perform while condition, asking to accept only number greater than 0, in order to count the digits.
 Increase the counter by 1, as the while condition approves.
 And eliminate the last digit of a number, in order to count.

int count = 0;
while(num>0) {
count++;
num = num/10;
}
[Link]("Number of digits in a number: "+count);

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Reverse digits of a number

Logic:
 Take a while loop , in order to take a input as a valid number.
 As it goes into while loop, trim the last digit from the number and consider it as a reverse.
 The number except the last number would be the new number, which will go into while loop again till we get the reverse of the given
number.

int rev = 0;
while(num>0) {
int temp=num%10;
rev = rev*10+temp;
num = num/10;
}
[Link](rev);

public class ReverseDigit {

static void main() {
Scanner sc = new Scanner([Link]);
ReverseDigit rd = new ReverseDigit();
int num = [Link]();
[Link]("Reverse Number: "+[Link](num));
}

public int reverse(int num) {

int rev = 0;
while(num>0) {
int temp=num%10;
 rev = rev*10+temp;
num = num/10;
}
return rev;
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Check if a number is Palindrome or not

Logic:
 Perform the same operation as reverse .

public class PalindromeNumber {

static void main() {
Scanner sc = new Scanner([Link]);
PalindromeNumber palindrome = new PalindromeNumber();
int num = [Link]();
if(num == [Link](num)) {
[Link]("Palindrome Number");
} else {
[Link]("Not Palindrome");
}
}

public int reverse(int num) {

int rev = 0;
while(num>0) {
int temp=num%10;
rev = rev*10+temp;
num = num/10;
}
return rev;
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

GCD of two numbers

Logic:
 The logic of this program is to find the Greatest Common Divisor (GCD) of two numbers by checking their common factors starting from
the largest possible factor.
 First, the program takes two integers as input using Scanner.
 Inside the gcd() method, it determines the smaller of the two numbers using [Link]() because the GCD cannot be greater than the
smaller number.
 Then a loop runs from this smaller number down to 1, checking whether the current value i divides both numbers (num1 % i == 0 and
num2 % i == 0).
 If i divides both numbers, it means i is a common factor.
 Since the loop starts from the largest possible value and moves downward, the first common factor found is the greatest common divisor,
which is immediately returned. If no common factor is found (which practically will not happen except for invalid cases), the method
returns -1.
 This approach is a brute-force method for GCD calculation.

public class GreatestCommonDivisor {

static void main() {
Scanner sc = new Scanner([Link]);
int num1 = [Link]();
int num2 = [Link]();

[Link]("Greatest Common Factor: "+gcd(num1, num2));

}
public static int gcd(int num1, int num2) {
int smallerNumber = [Link](num1, num2);
int factNum1 = 0;
int factNum2 = 0;
for(int i=smallerNumber; i>=1; i--) {
if(num1%i==0) {
factNum1 = i;
}
if(num2%i==0) {
factNum2 = i;
}
if(factNum1==factNum2 && factNum1!=0) return factNum1;
}
return -1;
}
}

Logic:
Logic: (Euclidean Algorithm)
The Euclidean Algorithm finds the GCD (Greatest Common Divisor) of two numbers based on the principle that subtracting the smaller
number from the larger number does not change their GCD. In the program, two numbers n1 and n2 are taken as input. A loop runs until one
of the numbers becomes 0. Inside the loop, the larger number is reduced by subtracting the smaller number (n1 = n1 - n2 or n2 = n2 - n1).
This process repeatedly reduces the values while preserving the same GCD. Eventually, one of the numbers becomes 0, and the remaining
non-zero number is the GCD of the original numbers. This method works because common divisors remain unchanged through repeated
subtraction.
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Check if the number is Armstrong

Logic:
This program checks whether a given number is an Armstrong number. In the main() method, the user enters a number using Scanner. The
program then calls the armstrong(num) method and compares its returned value with the original number. If both values are equal, the
program prints true, meaning the number is an Armstrong number; otherwise it prints false.
The armstrong(int num) method performs the main calculation. First, it finds the number of digits in the number by calling countDigits(num),
which determines the power to raise each digit. Then the program extracts each digit using num % 10, raises it to that power using [Link](),
and adds it to result. After processing each digit, the number is reduced using num = num / 10 until all digits are processed.
The countDigits(int num) method simply counts how many digits the number has by repeatedly dividing it by 10 until it becomes zero. For
example, if the input is 153, the program calculates 13+53+33=153. Since the calculated value equals the original number, it is an Armstrong
number.

public class ArmstrongNumber {

static void main() {
Scanner sc = new Scanner([Link]);
int num = [Link]();
boolean output = false;
if(num == armstrong(num)) {
output = true;
[Link](output);
} else {
[Link](output);
}

}
public static int armstrong(int num) {
int power = countDigits(num);
int result = 0;
while(num>0) {
result += (int) [Link]((num%10), power);
num = num/10;
}
return result;
}
public static int countDigits(int num) {
int count = 0;
while(num>0) {
num = num/10;
count++;
}
return count;
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Print all divisors (or factors)

Algorithm:
The brute force approach to find all the divisors of a number is to iterate through every number from 1 to N and check whether it is a divisor
or not. We can store all the divisors and return the list of divisors after iteration.

Time Complexity: O(N), we check for every number from 1 to N.

Space Complexity: O(N), extra space used for storing divisors.

public class NumberDivisors {

static void main() {
Scanner sc = new Scanner([Link]);
int num = [Link]();
List<Integer> result = divisors(num);
[Link](result);
}
public static List<Integer> divisors(int n) {
List<Integer> res = new ArrayList<>();
for(int i=1; i<=n; i++) {
if(n%i==0) [Link](i);
}
return res;
}
}

Algorithm:

public class NumberDivisors2 {

static void main() {
Scanner sc = new Scanner([Link]);
int num = [Link]();
List<Integer> result = allDivisors(num);
[Link](result);
}
public static ArrayList<Integer> allDivisors(int n) {
// Set<> to store unique values
Set<Integer> set = new HashSet<>();
for(int i=1; i<=(int)[Link](n); i++) {
if(n%i==0) {
[Link](i);
 [Link](n/i);
}
}
[Link](n); // n itself is a divisor
// For sorted list, we could have used TreeSet<>, but we have used list to sort.
List<Integer> list = new ArrayList<>(set);
[Link](list);
return (ArrayList<Integer>) list;
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Check for Prime number

Algorithm:
 First, a variable count is initialized to 0.
 A loop runs from 1 to num, and in each iteration it checks if num is divisible by i using num % i == 0. If the remainder is 0, it means i is a
divisor of num, so count is increased.
 After the loop finishes, the program checks the value of count. A prime number has exactly two divisors: 1 and itself. Therefore, if count
== 2, the number is prime and "True" is printed. Otherwise, it means the number has more than two divisors and is composite, so "False"
is printed.

int count=0; // to track the prime number, if count crosses 2 then it is composite number
for(int i=1; i<=num; i++) {
if(num%i==0) count++;
}
if(count==2) {
[Link]("True");
} else {
[Link]("False");
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Binary Search
 [Link]





































 s
Recursion

public class FunctionCallingItself {

public static void main(String[] args) {
shreyash(); // Non-static method 'shreyash()' cannot be referenced from a static context. So we made 'shreyash()' method static
}
public static void shreyash() {
[Link]("Anushree");
jayesh();
}
public static void jayesh() {
[Link]("Aakash");
aakash();
}
public static void aakash() {
[Link]("rahul");
shreyash();
}
}

 When a function calls itself, until a specified condition is met.

Segmentation → Stack overflow

 The base condition is the stopping point of a recursive function. It tells the function when to stop calling itself, so that it doesn’t go
on forever.
Without a base condition, a recursive function will call itself infinitely and cause a StackOverflowError (in Java).

The base condition (if (n == 0 || n == 1)) stopped recursion and started returning results back.
 A recursion tree is a diagram that shows how recursive function calls branch out — like a tree with the root as the first function call,
and its children as the recursive calls it makes.
◦ It helps you visualize:
▪ How many function calls are made.
▪ How values are combined.
▪ How recursion depth increases and decreases.
▪ The flow of execution (top-down and backtracking).

◦ What this shows:

▪ Each node = one function call
▪ Each branch = recursive calls inside it
▪ The height of the tree = recursion depth
▪ The number of nodes = total number of recursive calls

 Print N to 1

public class FunctionCallingItself {

public static void main(String[] args) {
print(5);
}
public static void print(int n) {
if(n==0) return; // base condition
[Link](n);
print(n-1); // method call
}
}

/*
OUTPUT
5
4
3
2
1
*/

 Print 1 to N using 2 parameters

import [Link];

public class OneToN {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
print(1, n);
}
public static void print(int i, int n) {
if(i>n) return; // stopping condition
 [Link](i);
print(i+1, n); // recursive call
}
}
/*
OUTPUT
i/p: 5
1
2
3
4
5
*/


public class Variables {
public static void main(String[] args) {
int x=10; // x is local to main()
change(x);
[Link](x); // 10
}
public static void change(int x) {
[Link](x); // 10
x=20;
[Link](x); // 20
}
}
In Java, method arguments are passed by value, not by reference. That means a copy of the value 10 is sent to the method — not the actual
variable from main.
Inside change(int x):
◦ The local variable x inside change() is a copy of the one in main().
◦ Initially, it prints 10.
◦ Then you reassign x = 20; → this changes only the local copy, not the one in main(). Prints 20.
◦ When the method finishes, its x variable is destroyed. The original x in main() is still 10.

public class GlobalVariables {

static int x=10; // global variable
public static void main(String[] args) {
fun();
[Link](x); // 20
}
public static void fun() {
[Link](x); // 10
x=20;
}
}

 Print 1 to N - using global variable

import [Link];

public class OneToN {

static int n; // global variable
public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
n=[Link](); // accessed global variable
print(1);
}
public static void print(int x) {
if(x>n) return; // base condition
[Link](x+" ");
print(x+1); //recursive call
}
}

/*
OUTPUT
i/p: 30
 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
*/

 Print 1 to N - using 1 parameter

import [Link];

public class OneToN {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n=[Link](); // accessed global variable
print(n);
}
public static void print(int n) {
if(n==0) return; // base case
print(n-1); //recursive call
[Link](n+" ");
}
}

/*
OUTPUT
i/p: 30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
*/

 Decreasing and increasing order – using single recursive function

public class DecreaseIncrease {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
print(n);
}
public static void print(int n) {
if(n==0) return;
[Link](n+" "); // Before recursive call → prints decreasing order
print(n-1);
[Link](n+" "); // After recursive call → prints increasing order
}
}

/*
OUTPUT
i/p: 5
5432112345
*/

 Decreasing and increasing order – without printing 1 twice

public class DecreaseIncrease {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n = [Link]();
print(n);
}
public static void print(int n) {
if(n==0) return;
[Link](n+" "); // Before recursive call → prints decreasing order
print(n-1);
if(n!=1) [Link](n+" "); // After recursive call → prints increasing order
}
}

/*
OUTPUT
i/p: 5
543212345
*/
 The if (n != 1) condition avoids printing 1 twice — because when n == 1, it prints 1 before recursion, and there’s no need to print it
again after returning.

 Factorial no.

public class Factorial {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n=[Link]();
[Link]("Factorial of "+n+" is: "+fact(n));
}
static int fact(int n) {
if(n==0 || n==1) return 1; // base case
int ans = n*fact(n-1);
return ans;
}
}

/*
OUTPUT
i/p: 5
Factorial of 5 is: 120
*/

public class Factorial {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n=[Link]();
[Link]("Factorial of "+n+" is: "+fact(n));
}
static int fact(int n) {
if(n==0 || n==1) return 1;
return n*fact(n-1);
}
}

/*
OUTPUT
i/p: 6
Factorial of 6 is: 720
*/

public class Factorial {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
int n=[Link]();
[Link]("Factorial of "+n+" is: "+fact(n));
}
static int fact(int n) {
return (n<=1) ? 1 : n*fact(n-1); // ternary operator
}
}

/*
OUTPUT
i/p: 5
Factorial of 5 is: 120
*/
 ‘a’ raised to the power ‘b’

int ans=1;
for(int i=1; i<=b; i++) {
ans *= a;
}
// TC: O(b)

ab = a * ab-1
264 → 2*263 → 2*262 → 2*261 → 2*260 ………………………..2*20 (N number of calls)
pow(a,b) = a* pow(a,b-1);
[Link](3,4) = 34 = 81.0

public class PowerLinear {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter base: ");
int a = [Link]();
[Link]("Enter exponent: ");
int b = [Link]();
[Link](a+" raised to the power "+b+" is: "+pow(a, b));
}
public static int pow(int a, int b) {
if(b==0) return 1;
return a*pow(a,b-1);
}
}

/*
OUTPUT
Enter base: 2
Enter exponent: 3
2 raised to the power 3 is: 8
*/

Logarithmic Time Complexity (divide and conquer approach)

ab = ab/2 * ab/2 (only corrrect in case b=even)
25=22*22 X → 25=22*22*2 V
ab = ab/2 * ab/2 * a (only corrrect in case b=odd)
264=232*232 → 232=216*216 → 216=28*28 → 28=24*24 → 24=22*22 → 22=21*21
6 = log264 calls

public class PowerLInear {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter base: ");
int a = [Link]();
[Link]("Enter exponent: ");
int b = [Link]();
[Link](a+" raised to the power "+b+" is: "+pow(a, b));
}
public static int pow(int a, int b) {
if(b==0) return 1; // base condition; anything raised to power 0 is 1
if(b%2==0) return pow(a,b/2)*pow(a,b/2); // if exponent b is even
else return a*pow(a,b/2)*pow(a,b/2); // if exponent b is odd
}
}

/*
OUTPUT
Enter base: 2
Enter exponent: 3
2 raised to the power 3 is: 8
*/
The inefficiency lies here: pow(a, b/2) * pow(a, b/2)
You’re calling pow(a, b/2) twice → same computation is repeated unnecessarily.
 For eg., to compute pow(2, 8), it calls pow(2, 4) two times, and each of those again calls pow(2, 2) twice, etc. That makes the total
number of recursive call exponential – roughly O(2log b)=O(b) again. So this loses the advantage of fast exponentiation.

public class PowerLinear {

public static void main(String[] args) {
Scanner sc = new Scanner([Link]);
[Link]("Enter base: ");
int a = [Link]();
[Link]("Enter exponent: ");
int b = [Link]();
[Link](a+" raised to the power "+b+" is: "+pow(a, b));
}
public static int pow(int a, int b) {
if(b==0) return 1; // base condition; anything raised to the power 0 is 1
int call = pow(a,b/2); // divides the pblm into half; each recursion call calculates a smaller power, until it reaches the base case
if(b%2==0) return call*call; // if exponent b is even
else return a*call*call;
}
}

/*
OUTPUT
Enter base: 2
Enter exponent: 3
2 raised to the power 3 is: 8
*/
TC: O(log b), SC: O(log b)
Your version divides the exponent by 2 each time:int call = pow(a,b/2);
That means recursion depth is proportional to log₂(b).

It seems you’re attempting to recursively compute: ab=(ab/2)2

That’s true only when b is even, but this code doesn’t handle the odd exponent case, nor the base case for b==0.
For eg.,
pow(2,4)
= pow(pow(2,2),2)
= pow(pow(2,1),2)
= pow(2,2)
= pow(pow(2,1),2)
→ infinite recursion! 😬
You end up calling pow(a, b/2) repeatedly with b=1 → pow(2,1) → returns 2, but then it becomes pow(2,2) again, forming a loop.
In other words, this code does not reduce the exponent properly to reach a stable base case for even numbers.

 POWER OF NUMBERS
Given a number n, find the value of n raised to the power of its own reverse.

class Solution {
public int reverseExponentiation(int n) {
// code here
int reverse=reverseNumber(n, 0);
return (int)[Link](n, reverse); // [Link] returns double; Calculate n^reverse
}
public static int reverseNumber(int n, int rev) { // recursive approach to reverse a number
if(n==0) return rev;
int digit=n%10; // extract last digit
return reverseNumber(n/10, rev*10+digit); // removing last digit, and adding digit to reversed number
 }
}

TC = O(digits) recursive calls. Since the number of digits d = log₁₀(n), we can also write: O(log₁₀ n) = O(log n)
Recursive reverse takes O(log n) time/space (digits of n), and [Link] adds another O(log n) time.

// REVERSE NUMBER (Common logic)

int num = 1234;
int rev = 0;
while(num != 0) {
rev *= 10; // extract last digit
rev += (num%10); // add digit to reversed number
num /= 10; // remove last digit
}
[Link](rev);














 s

--------------------------------------------------------------------------------
Array

 Linear data structure – all elements arranged sequentially.

 A collection of same data type stored at contiguous memory locations.

 Every array in memory has a base address, which is the memory location of the first element (index 0).
◦ The offset is the distance (in bytes) from his base address to another element in the array.
◦ Offset is calculated as: Offset = (index) x (size of each element)
◦ Address of ith element can be found using: Address of A[i] = Base address of A + (I x size of each element)

when you access arr[3], the system adds an offset of 12 bytes to the base address to reach that element.

 Is the array always of a fixed size?

◦ Arrays in Java are always of fixed size – once you create an aaray, its size cannot be changed during runtime.
◦ Declare and initialize an array:
int[] numbers = new int[5];
▪ Java allocates memory for exactly 5 integers.
▪ The size 5 becomes fixed and final for that array object.
▪ You cannot add or remove elements later – you can only modify existing elements.
▪ If you try to access or add the value to the index 5 or more, you will get ArrayIndexOutOfBoundsException, because valid
indexes are only 0 to 4.
◦ Why arrays are fixed-size?
▪ Java arrays are implemented as contiguous memory blocks – all elements are stored next to each other.
▪ Because of this, their size must be known at creation time, so Java can allocate exactly the right amount of memory.
◦ If you need a dynamic-sized array
▪ Use Collection class ArrayList, in which you can add, remove and resize freely.
▪ Internally, ArrayList uses an array that it resizes automatically when needed.
 When you create an ArrayList, it starts with a small array (default capacity = 10).
private Object[] elements = new Object[10];
 When you call add() and the array is full:
◦ A new, larger array is created (usually 1.5x or 2x the old size).
◦ All old elements are copied into the new array.
◦ The reference now points to the new array.
 This gives the illusion that the list grows automatically.
 ArrayList<Integer> list = new ArrayList<>();
[Link](10); // size = 1
[Link](20); // size = 2
...
// when size reaches current capacity (say 10)
// a new array of size 15 or 20 is created internally
 ArrayList hides this limitation by automatically creating a bigger array behind the scenes when needed.

 Array is a fundamental data structure and used to implement other data structure like stack, queue, dequeue and heap.

 Declaration of Array:
int arr[]; → This array will store integer type element
char arr[]; → This array will store char type element
float arr[]; → This array will store float type element

 Initialization of Array:
int arr[] = { 1, 2, 3, 4, 5 };
char arr[] = { 'a', 'b', 'c', 'd', 'e' };
float arr[] = { 1.4f, 2.0f, 24f, 5.0f, 0.0f };

 Array Operations:
◦ Accessing: O(1)
◦ Insert: O(1) / O(n)
◦ Delete: 0(1) / O(n)
◦ Traverse: O(n)
◦ Search: linear O(n) / binary O(log n)
◦ Update: O(1)
public class ArrayBasics {
public static void main(String[] args) {
// int num1 = 23;
// int num2 = 43;
// int num3 = 59;

int[] nums = {23, 43, 59, 71, 93, 20}; // initialized array
int size = [Link]; // Size of an array

// Indexing
[Link]("First element: "+nums[0]);
[Link]("Last element: "+nums[size-1]);

nums[0] = 37; // Update first element

// Display elements
for(int i=0; i<size; i++) {
[Link](nums[i]+" ");
}
[Link]();

int[] arr = new int[5]; // fixed array size

Scanner sc = new Scanner([Link]);
for(int i=0; i<[Link]; i++) {
arr[i] = [Link]();
}

for(int ele:nums) { // enhanced for loop

 [Link](ele+" ");
}
}
}

 Benefits:
◦ random access O(1): each element can be accessed directly using its index.
◦ cache friendly performance: Arrays are stored contiguously in memory, CPUs can prefetch nearby elements – making traversal
faster. This is why arrays outperform linked lists in iteration-heavy tasks.
◦ ease of sorting: Arrays have comntiguous memory and index-based access, which makes them very fast to sort. No pointer
chasing like in linked lists.
◦ implement other data structure: Arrays from building blocks of many higher-level data structures.
◦ many coding patterns

 Limitations:
◦ fixed size
◦ worst-case O(n) – insert, delete
◦ inefficient for frequent modifications

 Multi-dimensional arrays


 Pass by Value & Pass by Reference

When you pass an array, the value of arr is a reference (address) to the array. Both main() and change() points to the same array in memory. So,
it changes the original array.
main() num ──► [12, 34, 74, 23, 65]
change() num ─┘ (same memory)
Array is an object → reference is passed → change is visible
public class Array2Method {
public static void main(String[] args) {
int[] arr = {12, 34, 74, 23, 65};
[Link](arr[2]); // 74
change(arr);
[Link](arr[2]); // 99
}
public static void change(int[] arr) {
arr[2] = 99;
}
}

When you pass an integer, the value of num (ie., 12) is copied. The change() method works on a seperate copy, and original variable in
main() is untouched. That’s why change is NOT reflected.
Primitive value is passed → copy is modified → original unchanged
public class Integer2Method {
public static void main(String[] args) {
int num = 12;
[Link](num); // 12
changeNum(num);
[Link](num); // 12
}
public static void changeNum(int num) {
num = 100;
}
}

 Shallow Copy & Deep Copy

public class ShallowCopyDeepCopy {
public static void main(String[] args) {
//SHALLOW COPY (or REFERENCE COPY)
int[] arr = {10, 20, 30, 40}; // created in heap memory and stores the array object
int[] x = arr; // no new array is created; 'x' is a shallow copy of 'arr' -> means both point to the same memory location
x[0] = 100; // both references point to same array -> change is visible via 'arr'
[Link](arr[0]); // 100

// DEEP COPY
int[] arr2 = {11, 22, 33, 44};
// int[] y = [Link](arr2, [Link]); // using [Link]()
int[] y = [Link](); // new array 'y' is created; data is copied element by element
y[0] = 111;
 [Link](arr[0]); // 11
}
}

◦ Copying means creating a new variable/object from an existing one.

◦ Applies to array and objects. But NOT applicable to primitive data types.
◦ Types of Copy:
▪ Shallow Copy
 Copies reference only.
 No new object created.
 Both variables point to same memory.
 int[] arr = {10, 20};
int[] x = arr;

Memory view
STACK HEAP
----- ----
arr ───────────▶ [10, 20]
x ───────────▶ (both point to same heap object,
because only one array exists in heap)
(change in one ‘arr’ affects the other reference variable ‘x’ object)
 Object Example:
Student s1 = new Student();
Student s2 = s1; // shallow copy

STACK HEAP
----- ----
s1 ───────────▶ Student{id=10}
s2 ───────────▶ (same heap object)
▪ Deep Copy
 Copies actaul data.
 New object created.
 Both pbjects are independent.
 int[] arr = {10, 20};
int[] x = [Link]();

Memory view
STACK HEAP
----- ----
arr ───────────▶ [10, 20]
x ───────────▶ [10, 20]
(separate copy; two arrays exist in heap
arr and x point to different memory blocks.)
 Object Example:
Student s1 = new Student();
Student s2 = new Student(s1);

STACK HEAP
----- ----
s1 ───────────▶ Student{id=10}
s2 ───────────▶ Student{id=10}
(seperate objects; no shared memory)

◦ Java mainly uses two memory areas for this topic:

▪ Stack memory
 Stores local variables.
 Stores reference variables.
 Works in LIFO (Last In First Out) manner.
 Fast access.
 Automatically cleaned.
▪ Heap memory
 Stores objects and arrays.
 Shared among references.
 Cleaned by Garbage Collector.
▪ int[] arr = {10, 20, 30};
arr is stored in stack; actual array {10, 20, 30} stored in heap.
arr holds the address of that heap object.




 s
Given an array, print negative elements only

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

if(arr[i]<0) {
[Link](arr[i]+" ");
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Sum of all elements

int sum=0;
for(int ele:arr) {
sum+=ele;
}
[Link]("Sum of all elements: "+sum);

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Product of elements of the array

int prod = arr[0];

for(int i=1; i<[Link]; i++) {
prod*=arr[i];
}
[Link]("Product of elements: " + prod);

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Largest element

Brute → Better → Optimal

Algorithm:
 Sort an array.
 Return the last element of an array.
TC: O(n logn)
SC: O(1)

public static int FindLargest(int[] arr) {

[Link](arr);
 return arr[[Link]-1];
}

Algorithm:
 Consider first element as max.
 Iterate through other remaining elements, and check if any of those elements is greater than max or not, if yes, then update max value.
TC: O(n)
SC: O(1)

public static int FindLargest(int[] arr) {

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

Algorithm:
 Take a new variable and assign minimum value to it.
 Iterate through each element one by one, and check whether that element is greater than new variable or not. If the element appears
to be larger, then consider it as a maximum element.
TC: O(n), iterating through each element.
SC: O(1), extra variable required to store maximum element.

int[] arr = {2, 5, 1, 3, 0};

int max = Integer.MIN_VALUE;
for(int ele:arr) {
if(ele>max) max = ele;
}
[Link]("Largest element: "+max);

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Second smallest and second largest element in an array

Algorithm:
 Sort an array.
 Iterate through an array from the last second element, till first element (in reverse order).
 While iterating compare current element with the element before it (second last element with last element), and if they are not equal,
return iterated element.
TC: O(n) You perform a single reverse traversal of the array in the worst case (if all elements except the last are the same).
SC: O(1)

class Solution {
public int getSecondLargest(int[] arr) {
int size = [Link];
[Link](arr);
for(int i=size-2; i>=0; i--) {
if(arr[i] != arr[i+1]) return arr[i];
}
return -1;
}
}

Algorithm:
 The algorithm relies on the fact that the array is already sorted (if not, then sort an array first).
 The largest element is taken directly from the last index of the sorted array.
 To find the second largest distinct value, the array is scanned backwards starting from the second-last element.
 As soon as a value different from the largest is found, it is considered the second largest.
 The search stops immediately once this value is detected, ensuring an efficient lookup.
 This approach handles cases with duplicate values and negative numbers correctly.
TC: O(n) You perform a single reverse traversal of the array in the worst case (if all elements except the last are the same).
SC: O(1) Only a few extra variables (largest, secondLargest) are used, regardless of array size.

public static int FindSecondLargest(int[] arr) {

[Link](arr);
int size = [Link];
int largest = arr[size-1]; // 'largest' initialised to the last element of sorted array
int secondLargest = Integer.MIN_VALUE; // -2,14,74,83,648
for(int i=size-2; i>=0; i--) {
if(arr[i] != largest) {
secondLargest = arr[i];
break;
}
}
return secondLargest;
}

Algorithm (Without Sorting):

1. Identify the largest element
 The array is sorted once to easily locate the largest value.
 Since sorting arranges elements in ascending order, the last element becomes the largest.
2. Prepare to find the second largest
 A variable for the second largest value is initialized to the minimum possible number to safely compare against negative values
as well.
3. Scan the Array for the Second Largest Element
 The array is traversed again.
 For each element, the algorithm checks whether:
▪ It is greater than the current second largest, and
▪ It is not equal to the largest element found earlier.
 When both conditions are satisfied, that element becomes the new second largest.
4. After scanning, the stored value is returned as the second largest element.
TC: Sorting an array + Traversing array to find second largest = O(nlogn)+O(n) = O(nlogn) → sorting step dominates
SC: O(1) → If an in-place sorting algorithm is used (like [Link] in Java for primitives), the extra space is O(1). And only a few extra variables
(largest, secondLargest), so O(1) additional space.

public static int FindSecondLargest(int[] arr) {

int size = [Link];
int largest = largestELement(arr, size);
int secondLargest = Integer.MIN_VALUE;
for(int i=0; i<size; i++) {
if(arr[i]>secondLargest && arr[i]!=largest) {
secondLargest = arr[i];
}
}
return secondLargest;
}
public static int largestELement(int[] arr, int size) {
[Link](arr);
return arr[size-1];
}
This can also be code as:
if(arr[i]>secondLargest && arr[i]<largest) {
secondLargest = arr[i];
}

Algorithm:
1. Start by assuming the first element of the array is the largest, and initialize the second largest to the minimum possible value.
2. Loop through the array beginning from the second element (index 1).
3. If the current element is greater than the largest, then update the second largest to the old largest value, and set the current element
as the new largest.
4. Otherwise, if the current element is smaller than the largest but bigger than the second largest, update the second largest to the
current element.

public static int FindSecondLargest(int[] arr) {

int size = [Link];
int largest = arr[0];
int secondLargest = Integer.MIN_VALUE;

for(int i=1; i<size; i++) {

if(arr[i]>largest) {
secondLargest = largest;
largest = arr[i];
} else if(arr[i]<largest && arr[i]>secondLargest) {
secondLargest = arr[i];
}
}

return secondLargest;
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Alternating groups I

class Solution {
public int numberOfAlternatingGroups(int[] colors) {
int count=0;
int size = [Link];
for(int i=0; i<size; i++) {
if(i==0) {
if((colors[size-1]!=colors[i]) && (colors[i]!=colors[i+1])) count++;
} else if(i!=size-1) {
if((colors[i-1]!=colors[i]) && (colors[i]!=colors[i+1])) count++;
} else {
if((colors[i-1]!=colors[i]) && (colors[i]!=colors[0])) count++;
}
}
return count;
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Multiply odd inedxed elements by 2 and add 10 to even indexed elements

public class MultiplyOddEvenIndexed {

public static void main(String[] args) {
int[] arr = {21, 34,65, 83, 63, 27};
int size = [Link];

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

if(i%2==0) {
arr[i]+=10;
 } else {
arr[i]*=2;
}
}
for(int ele:arr) {
[Link](ele+" ");
}
}
}

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Remove duplicates from sorted array

I/P: arr = [1, 1, 2, 2, 2, 3, 3]

O/P: [1, 2, 3]

Algorithm
1. Insert all array elements into a set so that only unique values are kept (since a set automatically removes duplicates).
2. Create a new array with a size equal to the number of elements in the set.
3. Copy all elements from the set into this newly created array.
TC: O(n) + O([Link]) = O([Link])
SC: O(n)

import [Link];

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 2, 3, 3};

int[] result = RemoveDuplicates(arr);

for(int num: result) {
[Link](num+" ");
}
}
public static int[] RemoveDuplicates(int[] arr) {
int size = [Link];
HashSet<Integer> set = new HashSet<Integer>();
for(int i=0; i<size; i++) {
[Link](arr[i]);
}
// Adding HashSet elements to an Array
int[] newArray = new int[[Link]()];
int i=0;

for(int num:set) {
newArray[i++] = num;
}
return newArray;
}
}

Algorithm
1. Start with a sorted array.
 Place a pointer (first) at index 0.
 Use another pointer (current) starting from index 1 to compare elements.
2. Check for duplicates.
 If the element at current is equal to the element at first,
simply move the current pointer forward to continue searching for a different value.
3. Identify a new unique element.
 If the current element is different from the one at first
▪ increment first,
▪ copy the current element into this new first position,
▪ and increase the counter that tracks how many unique elements exist.
4. Build thee result array.
 After processing all elements, create a new array containing only the first counter number of elements (all unique).
 5. Return the new array contsaining only the unique values.
TC: Single pass through the array using two pointers O(n) + Creating a new array of unique elements O(k) = O(n)
SC: In-place duplicate removal O(1) + Creating a new array of size k O(k) = O(k)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 1, 2, 2, 2, 3, 3, 4, 4, 7}; // sorted array given

int[] result = RemoveDuplicates(arr);

for(int num: result) {
[Link](num+" ");
}
}
public static int[] RemoveDuplicates(int[] arr) {
int size = [Link];
int first=0;
int count=1; // to count the unique elements;
for(int i=1; i<size; i++) {
if(arr[i] != arr[first]) {
arr[++first] = arr[i];
count++;
}
}

int[] newArray = new int[count];

for(int i=0; i<count; i++) {
newArray[i] = arr[i];
}

return newArray;
}
}

Left rotate an array by one place

I/P: arr = [1, 2, 3, 4, 5]
O/P: [2, 3, 4, 5, 1]

Algorithm
1. Store the first element temporarily
 Save the element at index 0 in a temporary variable because it will be placed at the end after shifting.
2. Shift elements to the left
 Start iterating from index 1 to the last index.
 Move each element one position to the left (i.e., assign arr[i-1] = arr[i]).
3. Place the stored element at the end
 After completing the shift, insert the temporary element at the last index (arr[n-1]).
TC: You shift each of the remaining n-1 elements once O(n) + Placing the last element O(1) = O(n)
SC: Only one extra variable is used to store the first element O(1). If you are considering the returning array, then the SC would be O(n)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};

int[] result = leftRotate(arr);

for(int num: result) {
[Link](num+" ");
}
}
public static int[] leftRotate(int[] arr) {
int size = [Link];
int temp = arr[0];

for(int i=1; i<size; i++) {

arr[i-1] = arr[i];
if(i==size-1) {
arr[i] = temp;
}
}
 return arr;
}
}

Left rotate an array by D place(s)

I/P: arr = [1, 2, 3, 4, 5, 6], d=2
O/P: [3, 4, 5, 6, 1, 2]

Algorithm (using temporary array)

1. Store the first d elements
◦ Create a temporary array and copy the first d elements of the original array into it.
◦ Use a pointer j to track where to place elements inside the temporary array.
2. Shift the remaining elements to the left
◦ Starting from index d to the end of the array, shift each element to the left to overwrite earlier positions.
3. Place stored elements at the end-users
◦ After shifting, append the elements stored in the temporary array to the end of the original array.
◦ This completes the left rotation by d positions.
TC: Copying first d elements into temporary array O(d) + Shifting remaining (n – d) elements left O(n–d) + Copying temp elements to end O(d) =
O(n+d)
SC: You create a temporary array of size d O(d) + Returned resultant array O(n) = O(n)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};

int[] result = leftRotate(arr, 4);

for(int num: result) {
[Link](num+" ");
}
}
public static int[] leftRotate(int[] arr, int d) {
int size = [Link];
int[] tempArray = new int[d];
int j=0; // work as 'index' for 'tempArray'

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

if(i<d) { // store d places elements
tempArray[i] = arr[i];
} else if(i>=d) {
arr[i-d] = arr[i];
}
if(i >= size-d && i!=size) {
arr[i] = tempArray[j++];
}
}

return arr;
}
}
this logic can also be applied:
public static int[] leftRotate(int[] arr, int d) {
int size = [Link];
int[] tempArray = new int[d];

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

tempArray[i] = arr[i];
}

for(int i=d; i<size; i++) {

arr[i-d] = arr[i];
}

for(int i=size-d; i<size; i++) {

arr[i] = tempArray[i-(size-d)];
}
 return arr;
}

Algorithm
1. Reverse the first part of the array (from index 0 to d-1)
2. reverse the remaining elements of an array.
3. atlast, reverse the whole array. You will find that elements till dth place, placed at last and remaining elements of an array shifted left side.

public static int[] leftRotate(int[] arr, int d) {

d = d%[Link]; // if d is greater than the size of an array, this is used to normalise
reverse(arr,0, d);
reverse(arr, d, [Link]);
reverse(arr, 0, [Link]);
return arr;
}
public static void reverse(int[] arr, int start, int end) {
// in-place reverse
end--; // end index is exclusive
while(start<end) {
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}

Right rotate an array by one place

I/P: arr = [1, 2, 3, 4, 5]
O/P: [5, 1, 2, 3, 4]

1,2,3,4,5,6,7 → 7,6,5,4,3,2,1 → 7,1,2,3,4,5,6

Algorithm
 reverse an entire array, just to keep the last element at first position.
 Again reverse the element after first position till the end.
TC: O(n) + O(n-1) = O(n)
SC: O(1) → no extra space used

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
int[] result = leftRotationByOnePlace(arr);
for(int num:arr) {
[Link](num+" ");
}
}
public static int[] leftRotationByOnePlace(int[] arr) {
int n = [Link];
reverse(arr, 0, n);
reverse(arr, 1, n);
return arr;
}
static void reverse(int[] arr, int start, int end) {
end--; // end excluded
while(start<end) {
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
start++;
end--;
}
}
}
Right rotate an array by D place(s)
I/P: arr = [1, 2, 3, 4, 5, 6], d=2
O/P: [5, 6, 1, 2, 3, 4]

Algorithm
 Reverse the entire array
◦ Flips the whole sequence so that elements that need to move to the front shift closer to their final positions.
 Reverse two separate parts of the array:
◦ First part: reverse from index 0 to d-1
▪ (d-1 is the index, but it corresponds to the dth position)
◦ Second part: reverse from index d to n-1
▪ ( n is exclusive in typical programming loops)
 After these two segment reversals, the array becomes properly rotated, giving the final result.
TC: Reverse whole array → O(n) + Reverse first part (0 to d-1) → O(d) + Reverse second part (d to n-1) → O(n − d) = O(n)
SC:The reversals are done in-place, requiring no extra array. O(1)

123456→654321→561234

public static int[] rightRotate(int[] arr, int d) {

int n = [Link];
reverse(arr,0, n);
reverse(arr, 0, d);
reverse(arr, d, n);
return arr;
}
public static void reverse(int[] arr, int start, int end) {
// in-place reverse
end--; // end index is exclusive
while(start<end) {
int temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
start++;
end--;
}
}

Check if array is sorted

I/P: arr = [1, 2, 3, 4, 5, 6]
O/P: true

I/P: arr = [1, 2, 3, 4, 5, 9, 6, 7]

O/P: false

Algorithm (Using Nested loop)

 Check whether the array present in ascending order or not.
◦ If ith position element is not less than or equal to jth position element, then in that case return false.
◦ Else return true.
TC: O(N2)
SC: O(1)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 9, 7, 8}; // false
// int[] arr = {1, 2, 3, 4, 5, 7, 8}; // true
[Link](arrayIsSorted(arr));
}
public static boolean arrayIsSorted(int[] arr) {
int n = [Link];
for(int i=0; i<n-1; i++) {
for(int j=i+1; j<n; j++) {
if(arr[i] > arr[j]) {
return false;
}
}
}
return true;
 }
}

Algorithm
 iterate through an array from index 1 till the end.
 Check if previous element is less than or equals to the current element or not, if not then return false, else return true.
TC: O(N)
SC: O(1)

public static boolean arrayIsSorted(int[] arr) {

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

Move all zeroes to the end of the array

I/P: arr = [1, 0, 2, 3, 2, 0, 0, 4, 5, 1]
O/P: [1, 2, 3, 2, 4, 5, 1, 0, 0, 0]

I/P: arr = [1, 2, 3, 4, 5, 9, 6, 7]

O/P: [1, 2, 3, 4, 5, 9, 6, 7]

Algorithm (Using Temporary array)

 Allocate a temporary array of the same length as the original to hold the rearranged elements, placing all non-zero values first
followed by zeros.
 Traverse the original array and copy each non-zero element into the temporary array sequentially.
 Any remaining positions in the temporary array will naturally remain zero-filled.
 Return the temporary array as the final output.
TC: O(N)
SC: O(N)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 0, 2, 3, 2, 0, 0, 4, 5, 1};
int[] result = moveZeroesToTheEnd(arr);
for(int num:result) {
[Link](num+" ");
}
}
public static int[] moveZeroesToTheEnd(int[] arr) {
int n = [Link];
int[] tempArray = new int[[Link]];
int j=0; // to iterate through tempArray
for(int i=0; i<n; i++) {
if(arr[i]!=0) {
tempArray[j++] = arr[i];
}
// by default, java will add 0s at the remaining places of 'tempArray[]'
}
return tempArray;
}
}

Algorithm (Using Temporary array)

 Determine how many non-zero elements exist in the given array.
 If the count of non-zero elements is equal to the array length, return the array unchanged.
 Otherwise, allocate a temporary array sized exactly to the number of non-zero elements and copy all non-zero values into it.
 Copy the elements from this temporary array back into the original array, then fill the remaining positions with zeros.
 Return the updated original array as the final result.
TC: You scan the array once to count non-zero elements and again to rebuild the final array → O(N)
SC: Additional space is required for the temporary array holding only non-zero elements → O(k)
public static int[] moveZeroesToTheEnd(int[] arr) {
int n = [Link];

// Count non-zero elements present in given array

int count=0;
for(int i=0; i<n; i++) {
if(arr[i]!=0) count++;
}

// Create a new array of non-zero size

int[] tempArray = new int[count];
int j=0; // to iterate through tempArray
for(int i=0; i<n; i++) {
if(arr[i]!=0) {
tempArray[j++] = arr[i];
}
}

// Add non-zero from 'tempArray' to 'arr'

for(int i=0; i<n; i++) {
if(i<count) {
arr[i] = tempArray[i];
} else {
arr[i] = 0;
}
}
return arr;
}

Algorithm (Using two pointers)

 Verify whether the array has more than one element; if not, return it immediately.
 Set two pointers: i at index 0 and j at index 1, ensuring that j never goes beyond the array length.
 Evaluate four possible pointer conditions (nz 0, 0 nz, 0 0, nz nz):
◦ Case 1: i is zero and j is non-zero → swap their values, then advance both pointers.
◦ Case 2: i is non-zero and j is zero OR i and j are non-zero → no swap needed; simply move both pointers forward.
◦ Case 3: both i and j are zero → only move j ahead.
 Continue this process until j reaches the end, then return the updated array.
 Use standard element-swapping logic whenever a swap is required.
TC: Each pointer moves at most n steps, leading to a single linear pass → O(n)
SC: No extra space apart from a few variables; operations are performed in-place → O(1)

public static int[] moveZeroesToTheEnd(int[] arr) {

int n = [Link];
if(n<2) return arr; // in case arr carries only single element

int i=0, j=1;

while(j<n) { // 'while(i<=j)' will crash when j grows beyond array length.
if(arr[i]==0 && arr[j]!=0) {
swap(arr, i, j);
i++;
j++;
} else if((arr[i]!=0 && arr[j]==0) || (arr[i]!=0 && arr[j]!=0)) {
i++;
j++;
} else {
j++;
}
}
return arr;
}

static void swap(int[] arr, int i, int j) {

int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Linear search
I/P: arr = [6, 7, 8, 4, 1], num=4
O/P: 3 (return the index of first occurence)

Algorithm
 Traverse the array from start to end.
 If the target value matches any element during the scan, return its index; otherwise, return no result.
TC: In the worst case, every element is checked once → O(n)
SC: No additional memory is used beyond basic variables → O(1)

public class Solution {

public static void main(String[] args) {
int[] arr = {6, 7, 8, 4, 1};
[Link](linearSearch(arr, 4));
}
public static int linearSearch(int[] arr, int target) {
int n = [Link];
for(int i=0; i<n; i++) {
if(arr[i]==target) return i;
}
return -1;
}
}

Finding the union and intersection of two sorted arrays

I/P: int[] arr1 = {1, 2, 2, 3, 3, 4, 5, 6};
int[] arr2 = {2, 3, 3, 5, 6, 6, 7};
O/P: union[] = [1, 2, 3, 4, 5, 6]
intersection[] = [2, 3, 3, 5, 6]

Algorithm (FindUnion)
 Create a HashSet to store unique elements.
 Traverse arr1 and insert each element into the HashSet.
 Traverse arr2 and also insert elements into the same HashSet.
 Since a Set stores only unique values, duplicates are automatically removed.
 Convert the HashSet to a TreeSet to automatically sort the elements.
 Convert the TreeSet into an ArrayList and return it.
 If the target value matches any element during the scan, return its index; otherwise, return no result.
Time Complexity:
 Inserting all elements of arr1 into HashSet → O(m)
 Inserting all elements of arr2 into HashSet → O(n)
 Copying from HashSet to TreeSet (balanced BST) → O((m+n) log(m+n))
 Creating ArrayList from TreeSet → O(m+n)
= O((m+n) log(m+n))
Space Complexity:
 HashSet stores up to m + n elements → O(m + n)
 TreeSet also stores m + n → O(m + n)
 Result array list stores m + n (in worst case) → O(m + n)
= O(m+n)

Algorithm (FindIntersection)
 Create an empty list to store intersection elements.
 For each element in arr1:
◦ Loop through arr2 and compare elements.
◦ If both values match:
▪ Add the value to the list.
▪ Break the inner loop to avoid adding duplicates for the same arr1 element.
TC:
 Outer loop runs m times.
 Inner loop runs n times in the worst case.
 Therefore, total operations = m×n
= O(m*n)
SC: O(min(m,n))

public class Solution {

public static void main(String[] args) {
int[] arr1 = {1, 2, 2, 2, 3, 3, 4, 4, 5, 6};
 int arr2[] = {1, 3, 3, 6, 6, 7};
[Link](FindUnion(arr1, arr2));
[Link](FindIntersection(arr1, arr2));

}
public static List<Integer> FindUnion(int[] arr1, int[] arr2) {
int m = [Link];
int n = [Link];
// to add unique elements
Set<Integer> set = new HashSet<>();
for(int num:arr1) {
[Link](num);
}
for(int num:arr2) {
[Link](num);
}
// convert to TreeSet for sorted order
Set<Integer> set2 = new TreeSet<>(set);
return new ArrayList<>(set2);
}
public static List<Integer> FindIntersection(int[] arr1, int[] arr2) {
// int m = [Link];
// int n = [Link];
List<Integer> list = new ArrayList<>();
for(int num1:arr1) {
for(int num2:arr2) {
if(num1 == num2) {
[Link](num1);
break; // to avoid repetition
}
}
}
return list;
}
}

Algorithm (FindUnion)
 Use two pointers i and j, each starting at the beginning of arr1 and arr2.
 While both pointers are in range:
◦ If arr1[i] == arr2[j]:
▪ Add the element to the result list if it is not already present.
▪ Move both pointers forward.
◦ If arr1[i] < arr2[j]:
▪ Add arr1[i] to the result list if not already present.
▪ Move pointer i forward.
◦ If arr1[i] > arr2[j]:
▪ Add arr2[j] to the result list if not already present.
▪ Move pointer j forward
 After the loop, add any remaining elements of arr1 and arr2 to the result list (avoiding duplicates).
Time Complexity:
 Two-pointer traversal takes O(m + n)
 But [Link]() inside the loop takes O(k) time for each check, where k is current size of list.
 Worst case, this becomes: O((m + n) × (m + n)), because for each insert we may scan the list.
Space Complexity:
 Result list stores at most m + n unique elements → O(m+n)

Algorithm (FindINtersection)
 Use two pointers i and j.
 While both pointers are in array bounds:
◦ If arr1[i] == arr2[j]:
▪ Add value to result list.
▪ Move both pointers forward.
◦ If arr1[i] < arr2[j]:
▪ Add arr1[i] to the result list if not already present.
▪ Move pointer i forward.
◦ If arr1[i] > arr2[j]:
▪ Add arr2[j] to the result list if not already present.
▪ Move pointer j forward
 Since both arrays are sorted, values are compared in linear fashion.
Time Complexity:
 Each array is traversed at most once.
 Total operations = number of elements in both arrays.
O(m+n)
Space Complexity:
 Result list stores only common elements → O(min(m,n))

public class Solution {

public static void main(String[] args) {
int[] arr1 = {2, 3, 3, 5, 6, 6, 7};
int[] arr2 = {1, 2, 2, 3, 3, 4, 5, 6};

[Link](union(arr1, arr2)); // doesnot contains duplicates

[Link](intersection(arr1, arr2)); // common elements
}

public static List<Integer> union(int[] arr1, int[] arr2) {

int m = [Link];
int n = [Link];
ArrayList<Integer> list = new ArrayList<>();
int i=0, j=0;
while(i<m && j<n) {
if(arr1[i] == arr2[j]) {
if() {
[Link](arr1[i]);
}
i++;
j++;
} else if(arr1[i] < arr2[j]) {
if() {
[Link](arr1[i]);
}
i++;
} else if(arr1[i] > arr2[j]) {
if() {
[Link](arr2[j]);
}
j++;
}
}
while(i<m) {
if() {
[Link](arr1[i]);
}
i++;
}
while(j<n) {
if() {
[Link](arr2[j]);
}
j++;
}
return list;
}

public static List<Integer> intersection(int[] arr1, int[] arr2) {

int m = [Link];
int n = arr2. length;
ArrayList<Integer> list = new ArrayList<>();
int i=0, j=0;
while(i<m && j<n) {
if(arr1[i] == arr2[j]) {
[Link](arr1[i]);
i++;
j++;
} else if(arr1[i] < arr2[j]) {
i++;
} else if(arr1[i] > arr2[j]) {
j++;
 }
}
return list;
}
}

Array Duplicates
I/P: arr = [2, 3, 1, 2, 3]
O/P: [2, 3]
Explanation: 2 and 3 occir more than once in the given array

I/P: arr = [3, 1, 2]

O/P: []
Explanation: There is no repeating element in the array, so the output is empty

Algorithm (Using Nested for loops)

 Check very element with every other element using two nested loops.
 If a match is found,store the element in a result list (avoid adding it again).
TC:
 Outer loop → O(n)
 Inner loop → O(n)
 O(n2)
SC: Only result list is used → O(k) (distinct duplicates)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 2, 3, 1, 4, 5, 2};
[Link](findDuplicates(arr));
}
public static ArrayList<Integer> findDuplicates(int[] arr) {
ArrayList<Integer> list = new ArrayList<>();
int n = [Link];
for(int i=0; i<n-1; i++) {
for(int j=i+1; j<n; j++) {
if(arr[i] == arr[j]){
if() {
[Link](arr[i]);
}
}
}
}
return list;
}
}

Algorithm (HashSet)
 Use a HashMap or HashSet to track visited elements.
 If an element already exists, it is a duplicate.
 Much faster lookup: O(1) average for HashSet and HashMap.
TC: Single loop → O(n)
SC: Extra HashSet or HashMap → O(n)

public static ArrayList<Integer> findDuplicates(int[] arr) {

ArrayList<Integer> result = new ArrayList<>();
Set<Integer> seen = new HashSet<>();
for(int num:arr) {
if() { // if does not add the element, it means element already exists
if() {
[Link](num);
}
}
}
return result;
}

Algorithm (For sorted array or sorting first)

 First sort an array.
  Traverse linearly and compare adjacent elements.
 If arr[i] == arr[i + 1], it is a duplicate.
TC:
 Sorting → O(nlog n)
 Single scan → O(n)
O(nlogn)
SC: Sorting can be in-place → O(1)

public static ArrayList<Integer> findDuplicates(int[] arr) {

ArrayList<Integer> result = new ArrayList<>();
[Link](arr);
for(int i=0; i<[Link]-1; i++) {
if(arr[i] == arr[i+1]) {
if() {
[Link](arr[i]);
}
}
}
return result;
}

Mean and median of an array

I/P: arr = [1, 2, 19, 28, 5]
O/P: 11 5

I/P: arr = [2, 6, 8, 4]

O/P: 5 5

Mean: average value = sum of all the elements/total no. of elements

Median: average of two middle elements, after sorting

[Link](5.9) // 5.0 (rounds down to 5)

[Link](-2.3) // 3.0 (goes down to more negative)

Algorithm for FindMean(arr)

 Initialize a variable sum to 0.
 Iterate through each element of the array and accumulate all values into sum.
 Compute the mean by dividing sum by the number of elements.
 Return the floor value of the computed mean.
Algorithm for FindMedian(arr)
 Sort the array in ascending order.
 Compute the middle index as mid = length / 2.
 If the array size is even:
◦ Calculate the median as the average of the two middle values → (arr[mid − 1] + arr[mid]) / 2.
 If the array size is odd:
◦ The median is simply the element at index mid.
 Return the floor value of the median.
TC: FOR MEAN one traversal to compute the sum → O(n)
FOR MEDIAN sorting dominates the time → O(nlogn)
SC: FOR MEAN constant extra variables → O(1)
FOR MEDIAN if sorting in-place, like [Link] → O(n)

public class Solution {

public static void main(String[] args) {
int[] arr = {1, 2, 19, 28, 5};
[Link](FindMean(arr)+" "+FindMedian(arr)); // 11 5
}
public static int FindMean(int[] arr) {
int sum=0;
for(int i=0; i<[Link]; i++) {
sum+=arr[i];
}
int mean = sum/[Link];
return (int)[Link](mean);
}
public static int FindMedian(int[] arr) {
int median=0;
 [Link](arr);
int mid=[Link]/2;
if([Link]%2 == 0) {
median = (arr[mid-1]+arr[mid])/2;
} else {
median = arr[mid];
}
return (int)[Link](median);
}
}
You can either use bubble sorting (brute sorting) but the bad campared to Java in-built sorting, the time complexity for bubble sorting is O(n2)
Bubble sorting code:
public class Solution {
public static void main(String[] args) {
int[] arr = {2, 3, 1, 4, 7, 8, 5};
bubbleSort(arr);
for(int num:arr) {
[Link](num+" ");
}
}
public static void bubbleSort(int[] arr) {
int n = [Link];
for(int i = 0; i < n - 1; i++) {
// compare each pair
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
// swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
}

Missing in array
T/P: arr[] = [1, 2, 3, 5]
O/P: 4
Explanation: All the numbers from 1 to 5 are present except 4.

I/P: arr[] = [8, 2, 4, 5, 3, 7, 1]

O/P: 6
Explanation: All the numbers from 1 to 8 are present except 6.

I/P: arr[] = [1]

O/P: 2

Algorithm (Sorting method)

 The array is assumed to contain numbers from 1 to n, with one number missing.
 First, the array is sorted using [Link]().
 After sorting, a loop is run from index 0 to n−1.
 For each index i:
◦ The element that should have been present at that position is i + 1.
◦ If arr[i] != i + 1, it means this expected value is missing from the array.
◦ The missing value (i + 1) is returned immediately.
 If the loop completes without finding a mismatch, return n to indicate next element, as shown in example 3.
TC:
 Sorting the array using [Link]() → O(n log n)
 Single linear scan through the array → O(n)
= O(nlogn)
SC: Sorting happens in place, and only constant extra variables are used. → O(1) ignoring sorting implementation details.

public static int FindMissingNo(int[] arr) {

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

Algorithm (No sorting – Sum formula)

 Sum of numbers from 1 to n = n × (n + 1) / 2
 Compute:
◦ Total expected sum
◦ Sum of actual array elements
 Missing number = expectedSum − actualSum
TC: Iteration of an array elements → O(n)
SC: O(1)

public class Solution {

public static void main(String[] args) {
int[] arr = {2, 3, 1, 4, 7, 8, 5};
[Link](FindMissingNumber(arr));
}
public static int FindMissingNumber(int[] arr) {
int n = [Link]+1; // since one number is missing
int sumOfN = (n*(n+1))/2;
int sum=0;
for(int num:arr) {
sum += num;
}
return sumOfN-sum;
}
}

Algorithm (XOR method)

 XOR works because:
◦ X^X=0
◦ X^0=X
 XOR all numbers from 1 to n.
 XOR all elements in the array
 XOR both results → missing number remains
TC: Iteration of an array elements → O(n)
SC: O(1)

public class Solution {

public static void main(String[] args) {
int[] arr = {2, 3, 1, 4, 7, 8, 5};
FindMissingNumber(arr);
}
public static void FindMissingNumber(int[] arr) {
int n = [Link]+1; // since one number is missing
int xor1=0, xor2=0;
//XOR of numbers from 1 to n
for(int i=1; i<=n; i++) {
xor1 ^= i;
} // 1 ^ 3 ^ 0 ^ 4 ^ 1 ^ 7 ^ 0 ^ 8
for(int num:arr) {
xor2 ^= num;
} // 2 ^ 1 ^ 0 ^ 4 ^ 3 ^ 11 ^ 14
[Link](xor1^xor2); // 6
}
}
Sort 0s, 1s, and 2s
[Link]

Algorithm (Sorting)
 Use any sorting method (like [Link]).
TC: O(nlogn)
SC: O(1)

public void sort012(int[] arr) {

[Link](arr);
}

Algorithm (Counting Sort)

 Count number of 0s, 1s, and 2s.
 Rewrite array.
TC: O(n)
SC: O(1)

public static void sort012(int[] arr) {

int zeros=0, ones=0, twos=0;
for(int num:arr) {
if(num==0) zeros++;
else if(num==1) ones++;
else twos++;
}
int i=0, n=[Link];
while(zeros>0) {
arr[i++]=0;
zeros--;
}
while(ones>0) {
arr[i++]=1;
ones--;
}
 while(twos>0) {
arr[i++]=2;
twos--;
}
}

Kadane’s Algorithm
I/P: arr[] = [2, 3, -8, 7, -1, 2, 3]
O/P: 11
Explanation: The subarray [7, -1, 2, 3] has the largest sum 11.

I/P: arr[] = [-2, -4]

O/P: -2
Explanation: The subarray [-2] has the largest sum -2.

I/P: arr[] = [5, 4, 1, 7, 8]

O/P: 25
Explanation: The subarray [5, 4, 1, 7, 8] has the largest sum 25.

Algorithm
 Initialize maxSum with the first element.
 For each index i, treat it as the starting point of a subarray.
 Set currSum = 0 for each new i.
 From index i, keep adding elements one by one (j loop) to form subarrays.
 Update maxSum after each addition by comparing it with currSum.
 Continue until all possible subarrays have been evaluated.
 Return maxSum as the maximum subarray sum.
TC: O(n2)
SC: O(1)

public class Solution {

public static void main(String[] args) {
// int[] arr = {2, 3, -8, 7, -1, 2, 3};
// int[] arr = {-2, -4};
int[] arr = {5, 4, 1, 7, 8};

[Link]("Maximum sum of a subarray:"+FindMaxSubarraySum(arr));

}
public static int FindMaxSubarraySum(int[] arr) {
int n = [Link];
int maxSum=arr[0]; // excluding case of no elements included -> instead considering first element -> else we would be getting '0' in 2nd
case.

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

int currSum=0; // each new ith value, we would be considering ‘currSum’ be 0 → for the fresh subarray sum.
for(int j=i; j<n; j++) {
currSum+=arr[j];
maxSum = [Link](maxSum,currSum);
}
}
return maxSum;
}
}

Algorithm (Kadane’s algorithm)

 Iterate through an array, and keep adding items to current sum.
 If current sum becomes negative → reset to 0.
 Track the maximum so far.
TC: O(n)
SC: O(1)

public static int FindMaxSubarraySum(int[] arr) {

int n = [Link];
int maxSoFar=Integer.MIN_VALUE;
int currSum=0;
 for(int num:arr) {
currSum+=num;
maxSoFar = [Link](maxSoFar, currSum);
if(currSum<0) {
currSum=0;
}
}
return maxSoFar;
}

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

16. Array Leaders

I/P: arr = [16, 17, 4, 3, 5, 2]

O/P: [17, 5, 2]
Explanation: Note that there is nothing greater on the right side of 17, 5 and, 2.

I/P: arr = [10, 4, 2, 4, 1]

O/P: [10, 4, 4, 1]
Explanation: Note that both of the 4s are in output, as to be a leader an equal element is also allowed on the right. side

I/P: arr = [5, 10, 20, 40]

O/P: [40]
Explanation: When an array is sorted in increasing order, only the rightmost element is leader.

I/P: arr = [30, 10, 10, 5]

O/P: [30, 10, 10, 5]
Explanation: When an array is sorted in non-increasing order, all elements are leaders.

Algorithm (Nested for loops)

 For every element arr[i], check all elements to its right.
 Assume arr[i] is a leader initially (isLeader = true).
 If any element to the right is greater, mark it as not a leader.
 If after checking all elements to the right it remains true, add it to the result list.
 Continue this for all elements in the array.
 Return the list of elements that passed the leader condition.
TC: O(n2)
SC: O(k)

public class Solution {

public static void main(String[] args) {
// int[] arr = {16, 17, 4, 3, 5, 2};
// int[] arr = {10, 4, 2, 4, 1};
int[] arr = {5, 10, 20, 40};
// int[] arr = {30, 10, 10, 5};

[Link]("Array Leader:" + FindArrayLeader(arr));

}

public static ArrayList<Integer> FindArrayLeader(int[] arr) {

ArrayList<Integer> list = new ArrayList<>();
int n = [Link];

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

boolean isLeader = true;
for(int j=i+1; j<n; j++) {
if(arr[j] > arr[i]) { // if in second iteration, element is found to be greater than ith element, then the ith element cannot be a leader.
isLeader = false;
break; // we will not go further, as we have found greater element on right side of an ith element.
}
}
if(isLeader) [Link](arr[i]);
}

return list;
}
}
Algorithm (one pass)
 Initially store max value, as minimum as possible.
 Later we iteratean array in reverse order, to keep the track of right-most max element one-by-one.
 If current element in an array founds to be greate than equal to the max value so far, we update the max value, and add the max
element in a list.
 Reverse the list and return it as a result.
TC: O(n)
SC: O(k)

public class Solution {

public static void main(String[] args) {
// int[] arr = {16, 17, 4, 3, 5, 2};
// int[] arr = {10, 4, 2, 4, 1};
// int[] arr = {5, 10, 20, 40};
int[] arr = {30, 10, 10, 5};

[Link]("Array Leader:" + FindArrayLeader(arr));

}

public static ArrayList<Integer> FindArrayLeader(int[] arr) {

ArrayList<Integer> list = new ArrayList<>();
int n = [Link];
int maxSoFar=Integer.MIN_VALUE; // track the max value from right -> left
for(int i=n-1; i>=0; i--) {
if(arr[i]>=maxSoFar) {
maxSoFar=arr[i];
[Link](maxSoFar);
}
}
[Link](list);
return list;
}
}

Missing and Repeating

Given an unsorted array arr[] of size n, containing elements from the range 1 to n, it is known that one number in this range is missing, and
another number occurs twice in the array, find both the duplicate number and the missing number.

Algorithm
 I
TC: O(n2)
SC: O(1)

Two Sum
Time complexity: O(n)

Logic 2: Time complexity: O(n^2)

If interviewer says:

“Array is unsorted”

👉 Use HashMap (O(n))

If interviewer says:

“Array is sorted”

👉 Use Two Pointer (best)

Binary Search (for sorted array)

[Link]
Logic 1: If there is no repetitive elements in an array.
class Solution {
public int binarysearch(int[] arr, int k) {

int start = 0;
int end = [Link]-1;

while(start<=end) {
// int mid = (end-start)/2; // ❌ This gives an index relative to 0, not to start.
int mid = start + (end-start)/2;
if(arr[mid] == k) {
return mid; // Use 'return' or 'break' to stop after finding the element
} else if(arr[mid] > k) {
// end = mid; // ❌ This can cause infinite loop because mid doesn’t change.
end = mid-1;
} else {
// start = mid; // ❌ This can cause infinite loop because mid doesn’t change.
start = mid+1;
}
}
return -1;
}
}

Logic 2: If 1st occurrence of element is asked, in case of repetitive elements.

First occurrence = move left on match
Last occurrence = move right on match
class Solution {
public int binarysearch(int[] arr, int k) {

int start = 0;
int end = [Link] - 1;
int ans = -1;

while (start <= end) {

int mid = start + (end - start) / 2;
if (arr[mid] == k) {
ans = mid; // store possible answer
end = mid - 1; // move left
} else if (arr[mid] > k) {
end = mid - 1;
} else {
start = mid + 1;
}
}

if (ans != -1) return ans;

else return ans;
}
}

Parenthesis Checker

[Link]

Equilibrium Point

[Link]

Algorithm(TC: O(n^2), SC: O(1))

 Ignore the first and last index, because they can’t have elements on both sides.
 Pick one index i in the middle.
 Add all numbers before i → this is leftSum.
  Add all numbers after i → this is rightSum.
 If leftSum == rightSum, then:
◦ i is the equilibrium point
◦ stop checking further.
 If no such index is found, return -1.

 What checkSum() does

◦ It simply adds numbers between two given positions in the array.
◦ Used to calculate left and right sums.

class Solution {
// Function to find equilibrium point in the array.
public static int findEquilibrium(int arr[]) {
int size = [Link];
int ans = -1;

int first = 0;
int last = size-1;
for(int i=1; i<size-1; i++) {
int leftSum = CheckSum(first, i-1, arr);
int rightSum= CheckSum(i+1, last, arr);
if(leftSum == rightSum) {
ans = i;
break;
}
}
if(ans != -1) {
return ans;
} else return ans;
}
public static int CheckSum(int first, int last, int[] arr) {
int sum=0;
for(int i=first; i<=last; i++) {
sum+=arr[i];
}
return sum;
}
}

Algorithm(TC: O(n), SC: O(N)) → PREFIX SUM

 Make a new array where each index stores sum till that index.
 Total sum is the last value of prefix array
 For each middle index:
◦ Left sum = value before index
◦ Right sum = total − sum till index
 If both sums are equal → equilibrium index

class Solution {
// Function to find equilibrium point in the array.
public static int findEquilibrium(int arr[]) {
int n = [Link];

// If array has only one element

if (n == 1) return 0;

// Step 1: Create prefix sum array

int[] prefix = new int[n];
prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
prefix[i] = prefix[i - 1] + arr[i];
}

int totalSum = prefix[n - 1];

// Step 2: Check equilibrium condition

for (int i = 1; i < n - 1; i++) {
int leftSum = prefix[i - 1];
int rightSum = totalSum - prefix[i];
 if (leftSum == rightSum) {
return i;
}
}

return -1;
}
}

Algorithm(TC: O(n), SC: O(1))

 First, add all numbers of the array → this is totalSum.
 Start with left side sum as the first element
 Move index one by one from left to right (ignore first & last index)
 For each index:
◦ Right sum = total sum − (left sum + current element)
◦ If left sum == right sum, this index is the answer
 If no index matches, return -1

class Solution {
// Function to find equilibrium point in the array.
public static int findEquilibrium(int arr[]) {
int size = [Link];
int totalSum = 0;
for(int i=0; i<size; i++) {
totalSum+=arr[i];
}
int ans = -1;
int leftSum = arr[0];
for(int i=1; i<size-1; i++) {
if(leftSum == (totalSum-(leftSum+arr[i]))) {
ans = i;
break;
}
leftSum+=arr[i];
}
if(ans != -1) return ans;
else return ans;
}
}

Parenthesis Checker

[Link]