CS & IT
ENGINEERING
Java With OOPs
OOPs using JAVA
DPP 01(Discussion Notes) By- Aditya sir
Topics to be Covered
Topic DPP Questions Discussion
Practice full
[SUB]
#Q. Problem statement: You are given an array nums containing n elements, where
each element represents a color:
• 0 for red
• 1 for white
• 2 for blue
Your task is to sort the array in-place so that objects of the same color are
grouped together, in the order red (0), white (1), then blue (2).
Important:
• You cannot use any built-in sort functions.
• The solution should ideally be a one-pass algorithm that uses only constant
extra space.
Example 1:
Input: nums = [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]
Example 2:
Input: nums = [2,0,1]
Output: [0,1,2]
Constraints:
• 1 <= [Link] <= 300
• Each nums[i] is either 0, 1, or 2.
Follow-up:
Can you design a one-pass solution that sorts the array using only constant extra
space?
[SUB]
#Q. Problem statement: You are given a sorted array arr[] of size n.
The task is to rearrange the array in-place so that all distinct elements appear at
the start of the array in sorted order.
After moving the distinct elements to the front, return the number of distinct
elements found. The elements beyond the distinct portion of the array can hold
any values, as they don't affect the result.
Examples:
Input: arr[] = [2, 2, 2, 2, 2]
Output: 1 (array becomes [2])
Explanation: Only one unique element (2) is present.
Input: arr[] = [1, 2, 2, 3, 4, 4, 4, 5, 5]
Output: 5 (array becomes [1, 2, 3, 4, 5])
Input: arr[] = [1, 2, 3]
Output: 3 (array remains [1, 2, 3])
Explanation: All elements are already distinct.
Constraints:
• 1 <= n <= 10^4
• Array is sorted in non-decreasing order.
[SUB]
#Q. Problem statement: Given an array arr[], your task is to identify all the leaders in
the array.
An element is called a leader if it is greater than or equal to all the elements to its
right in the array.
By default, the last element in the array is always considered a leader since there
are no elements after it.
Examples:
Input: arr[] = [16, 17, 4, 3, 5, 2]
Output: [17, 5, 2]
Input: arr[] = [1, 2, 3, 4, 5, 2]
Output: [5, 2]
[SUB]
#Q. Problem statement: You are given an unsorted array of size n, containing
numbers ranging from 1 to n.
In this array:
• One number is missing from the range {1, 2, …, n}
• One number appears twice
Your task is to find the repeating number and the missing number.
Examples:
Input: arr[] = {3, 1, 3}
Output: 3, 2
Explanation: Number 2 is missing, and 3 occurs twice.
Input: arr[] = {4, 3, 6, 2, 1, 1}
Output: 1, 5
Explanation: Number 5 is missing, and 1 repeats.
HashMap
Yumes
Ty
1ton
1 o 3 354 sept
a
0
01
3 50
2 0
i o
3 012
[SUB]
#Q. Problem statement: You are given an array prices[] of length N, where each
element represents the price of a stock on a particular day.
Your task is to find the maximum profit that can be made by performing exactly
one transaction — meaning buying one stock and selling it later.
Note: You must buy the stock before you sell it.
Examples:
Input: prices[] = {7, 10, 1, 3, 6, 9, 2}
Output: 8
Explanation: Buy at 1 and sell at 9 for a profit of 8.
Input: prices[] = {7, 6, 4, 3, 1}
Output: 0
Explanation: No profit can be made as prices keep decreasing.
Input: prices[] = {1, 3, 6, 9, 11}
Output: 10
Explanation: Buy at 1 and sell at 11 for a profit of 10.
[SUB]
#Q. Problem statement: You are given an array prices[] of size n, where each element
represents the price of a stock on a particular day.
The task is to calculate the maximum profit possible if you are allowed to buy
and sell the stock any number of times.
Note:
• You must sell the stock before you can buy it again (no multiple holdings
allowed at the same time).
• You can buy and sell on the same day if it’s profitable.
Examples:
Input: prices[] = {100, 180, 260, 310, 40, 535, 695}
Output: 865
Explanation:
• Buy on day 0, sell on day 3 → Profit = 310 - 100 = 210
• Buy on day 4, sell on day 6 → Profit = 695 - 40 = 655
• Total Profit = 210 + 655 = 865
Input: prices[] = {4, 2, 2, 2, 4}
Output: 2
Explanation:
• Buy on day 3, sell on day 4 → Profit = 4 - 2 = 2
• Total Profit = 2
[SUB]
#Q. Problem statement: Given an array arr[] of n integers, your task is to create a
new array res[] of the same size such that each element res[i] is equal to the
product of all the elements in arr[] except arr[i].
Examples:
Input: arr[] = [10, 3, 5, 6, 2]
Output: [180, 600, 360, 300, 900]
Explanation: • res[0] = 3 × 5 × 6 × 2 = 180
• res[1] = 10 × 5 × 6 × 2 = 600
• res[2] = 10 × 3 × 6 × 2 = 360
• res[3] = 10 × 3 × 5 × 2 = 300
• res[4] = 10 × 3 × 5 × 6 = 900
input: arr[] = [12, 0]
Output: [0, 12]
Explanation: • res[0] = 0
• res[1] = 12
[SUB]
#Q. Problem statement: Given an array arr[], the task is to find the contiguous
subarray with the maximum possible sum and return that sum.
Examples:
Input: arr[] = {2, 3, -8, 7, -1, 2, 3}
Output: 11
Explanation: The subarray {7, -1, 2, 3} has the highest sum of 11.
Input: arr[] = {-2, -4}
Output: -2
Explanation: The subarray {-2} gives the maximum sum -2.
Input: arr[] = {5, 4, 1, 7, 8}
Output: 25
Explanation: The entire array {5, 4, 1, 7, 8} has the largest sum 25.
[SUB]
#Q. Problem statement: You are given an unsorted array arr[] that contains both
positive and negative numbers. Your task is to find the smallest positive number
missing from the array.
Note: You are allowed to modify the original array.
Examples:
Input: arr[] = {2, -3, 4, 1, 1, 7}
Output: 3
Explanation: The smallest positive number missing from the array is 3.
Input: arr[] = {5, 3, 2, 5, 1}
Output: 4
Explanation: The smallest positive number missing from the array is 4.
Input: arr[] = {-8, 0, -1, -4, -3}
Output: 1
Explanation: The smallest positive number missing from the array is 1.
[SUB]
#Q. Problem statement: You are given an array of n distinct integers. Your task is to
find the third largest element in the array.
Examples:
Input: arr[] = {1, 14, 2, 16, 10, 20}
Output: 14
Explanation: The largest element is 20, the second largest is 16, and the third
largest is 14.
Input: arr[] = {19, -10, 20, 14, 2, 16, 10}
Output: 16
Explanation: The largest element is 20, the second largest is 19, and the third
largest is 16.
[SUB]
#Q. Problem Statement: Given an integer array nums and an integer target, return
indices of the two numbers such that they add up to target. You must achieve an
average O(n) runtime by using a Map<Integer,Integer> to store seen values.
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: nums[0] + nums[1] == 9
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
[SUB]
#Q. Problem Statement: Given a string s, find the index of the first non-repeating
character in it. If it doesn’t exist, return -1.
Example 1:
Input: s = "adityajainsir"
Output: 0
Explanation: 'd' is the first character that appears only once, at index 0.
Example 2:
Input: s = "aadiyajainsir"
Output: 6
Explanation: 'j' is the first non-repeating character, at index 6.
[SUB]
#Q. Problem Statement: Given two integer arrays nums1 and nums2, return their
intersection, including duplicates.
Each element in the result should appear as many times as it shows in both
arrays. You may return the result in any order. Use a Map<Integer,Integer> to
count one array, then collect from the other into an ArrayList<Integer>.
Example 1:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] 51
A
Output: [4,9]
52
Explanation: Both 4 and 9 appear in both arrays. A2
Example 2:
Input: nums1 = [1,2,2,1], nums2 = [2,2] am
SIM
Output: [2,2]
Logic
Hada hmI hm
nd clue
Array comon
41
1 a
2 2
chutnet
Arrays add elem
am
hmfelu
[SUB]
#Q. Problem Statement: Given an array of strings strs, group the anagrams together.
Return the result as a list of groups (each group is a List<String>). You can use a
Map<String,List<String>>, where the key is the sorted-character signature of
each word.
Example 1:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["eat","tea","ate"],["tan","nat"],["bat"]]
Example 2:
Input: strs = [""]
Output: [[""]]
[SUB]
#Q. Problem Statement: Given an integer array arr, return true if the number of
occurrences of each value in the array is unique, otherwise return false. Use a
Map<Integer,Integer> to count frequencies, then a Set<Integer> to check for
duplicate counts.
Example 1:
Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: Occurrences are {1→3, 2→2, 3→1}, all counts are unique.
Example 2:
Input: arr = [1,2]
Output: false
Explanation: Both 1 and 2 occur once → duplicate occurrence count.
THANK - YOU