.png)
coding Q & A
- Anand Nerurkar
- Aug 17
- 10 min read
find out index in array whose two sum is 6
import java.util.*;
public class TwoSumHashMap {
public static void main(String[] args) {
int[] nums = {1, 3, 2, 4, 5};
int target = 6;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
System.out.println("Indices: " + map.get(complement) + ", " + i);
return;
}
map.put(nums[i], i);
}
Integer to Roman
=====
public class IntegerToRoman {
public static String intToRoman(int num) {
// Roman numeral mappings
int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1}
String[] symbols = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"
};
StringBuilder sb = new StringBuilder();
for (int i = 0; i < values.length; i++) {
while (num >= values[i]) {
num -= values[i];
sb.append(symbols[i]);
}
}
return sb.toString();
}
public static void main(String[] args) {
System.out.println("3 -> " + intToRoman(3)); // III
System.out.println("9 -> " + intToRoman(9)); // IX
System.out.println("58 -> " + intToRoman(58)); // LVIII
System.out.println("1994 -> " + intToRoman(1994)); // MCMXCIV
}
}
}
}
Roman to Intger
====
import java.util.*;
public class RomanToInteger {
public static int romanToInt(String s) {
// Roman numeral mappings
Map<Character, Integer> map = new HashMap<>();
map.put('I', 1);
map.put('V', 5);
map.put('X', 10);
map.put('L', 50);
map.put('C', 100);
map.put('D', 500);
map.put('M', 1000);
int total = 0;
int prevValue = 0;
// Traverse from right to left
for (int i = s.length() - 1; i >= 0; i--) {
int currentValue = map.get(s.charAt(i));
if (currentValue < prevValue) {
total -= currentValue; // subtract in cases like IV, IX, XL, etc.
} else {
total += currentValue;
}
prevValue = currentValue;
}
return total;
}
public static void main(String[] args) {
System.out.println("III -> " + romanToInt("III")); // 3
System.out.println("IX -> " + romanToInt("IX")); // 9
System.out.println("LVIII -> " + romanToInt("LVIII")); // 58
System.out.println("MCMXCIV -> " + romanToInt("MCMXCIV")); // 1994
}
}
longest palindrome in substring
====
public class LongestPalindromeSubstring {
public static String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
for (int i = 0; i < s.length(); i++) {
// Odd length palindrome
int len1 = expandAroundCenter(s, i, i);
// Even length palindrome
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private static int expandAroundCenter(String s, int left, int right) {
while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
left--;
right++;
}
return right - left - 1; // length of palindrome
}
public static void main(String[] args) {
System.out.println(longestPalindrome("babad")); // bab or aba
System.out.println(longestPalindrome("cbbd")); // bb
System.out.println(longestPalindrome("a")); // a
System.out.println(longestPalindrome("forgeeksskeegfor")); // geeksskeeg
}
}
detect capital in string
=====
public class DetectCapital {
public static boolean detectCapitalUse(String word) {
int n = word.length();
// Case 1: All uppercase
if (word.equals(word.toUpperCase())) return true;
// Case 2: All lowercase
if (word.equals(word.toLowerCase())) return true;
// Case 3: Only first letter uppercase
if (Character.isUpperCase(word.charAt(0)) &&
word.substring(1).equals(word.substring(1).toLowerCase())) {
return true;
}
// Otherwise false
return false;
}
public static void main(String[] args) {
System.out.println(detectCapitalUse("USA")); // true
System.out.println(detectCapitalUse("leetcode")); // true
System.out.println(detectCapitalUse("Google")); // true
System.out.println(detectCapitalUse("FlaG")); // false
}
}
power of4
===
public class PowerOfFour {
public static boolean isPowerOfFour(int n) {
if (n <= 0) return false;
while (n % 4 == 0) {
n /= 4;
}
return n == 1;
}
public static void main(String[] args) {
System.out.println(isPowerOfFour(16)); // true
System.out.println(isPowerOfFour(5)); // false
System.out.println(isPowerOfFour(64)); // true
System.out.println(isPowerOfFour(1)); // true
}
}
public static boolean isPowerOfFour(int n) {
if (n <= 0) return false;
double logVal = Math.log(n) / Math.log(4);
return logVal == (int) logVal; // check if integer
}
reverse astring
===
public class ReverseString {
public static String reverse(String str) {
return new StringBuilder(str).reverse().toString();
}
public static void main(String[] args) {
System.out.println(reverse("hello")); // "olleh"
System.out.println(reverse("anand")); // "dnana"
}
}
Given an array of size n-1 containing distinct integers from 1 to n, find the missing number.
=================
✅ Approach 1: Using Formula (Sum of First n Natural Numbers)
Sum of first n natural numbers = n*(n+1)/2
Subtract the sum of array elements from it → gives missing number.
public class MissingNumber {
public static int findMissing(int[] nums, int n) {
int expectedSum = n * (n + 1) / 2;
int actualSum = 0;
for (int num : nums) {
actualSum += num;
}
return expectedSum - actualSum;
}
public static void main(String[] args) {
int[] nums = {1, 2, 4, 5, 6}; // n = 6, missing = 3
System.out.println("Missing Number: " + findMissing(nums, 6));
}
}
Output:
Missing Number: 3Find the minimum number in a sorted and rotated array(Array is sorted in ascending order but rotated at some pivot).
Example:
Input: [4, 5, 6, 7, 0, 1, 2]
Output: 0
public class FindMinInRotatedArray {
// Recursive function to find minimum in rotated sorted array
public static int findMin(int[] a, int l, int r) {
// Base case: only one element
if (l == r) return a[l];
// If the subarray is already sorted, return leftmost element
if (a[l] < a[r]) return a[l];
int mid = (l + r) / 2;
// If mid element is greater than rightmost, min is in right half
if (a[mid] > a[r]) {
return findMin(a, mid + 1, r);
} else {
// Otherwise, min is in left half (including mid)
return findMin(a, l, mid);
}
}
// Main method
public static void main(String[] args) {
int[] arr = {4, 5, 6, 7, 0, 1, 2}; // Example rotated sorted array
int n = arr.length;
int minElement = findMin(arr, 0, n - 1);
System.out.println("The minimum element in the rotated array is: " + minElement);
}
}
minimum no of paltform reuired for a station
====
import java.util.Arrays;
public class MinPlatforms {
public static int minPlatforms(int[] arr, int[] dep) {
Arrays.sort(arr);
Arrays.sort(dep);
int i = 0, j = 0, platforms = 0, maxPlat = 0;
int n = arr.length;
while (i < n && j < n) {
if (arr[i] <= dep[j]) { // arrival needs a platform
platforms++;
maxPlat = Math.max(maxPlat, platforms);
i++;
} else { // a train departed, free a platform
platforms--;
j++;
}
}
return maxPlat;
}
public static void main(String[] args) {
int[] arrivals = {900, 940, 950, 1100, 1500, 1800};
int[] departures = {910, 1200, 1120, 1130, 1900, 2000};
System.out.println(minPlatforms(arrivals, departures)); // 3
}
}
find a pair whose sum id closet to zero
===
Efficient Approach (O(n log n))
Sort the array.
Use two pointers (left = 0, right = n-1).
Compute sum:
If |sum| < |closest|, update the result.
If sum < 0, move left++ (to increase sum).
Else move right-- (to decrease sum).
Continue until left < right.
💻 Java Code
import java.util.Arrays;
public class ClosestToZeroPair {
public static void findPairClosestToZero(int[] arr) {
if (arr.length < 2) {
System.out.println("Array must have at least 2 elements");
return;
}
// Step 1: Sort the array
Arrays.sort(arr);
int left = 0, right = arr.length - 1;
int minLeft = left, minRight = right;
int closestSum = Integer.MAX_VALUE;
// Step 2: Use two-pointer technique
while (left < right) {
int sum = arr[left] + arr[right];
// Update closest sum if better found
if (Math.abs(sum) < Math.abs(closestSum)) {
closestSum = sum;
minLeft = left;
minRight = right;
}
// Move pointers based on sum
if (sum < 0) {
left++; // Need a bigger sum
} else {
right--; // Need a smaller sum
}
}
System.out.println("Pair: (" + arr[minLeft] + ", " + arr[minRight] +
") with sum closest to zero = " + closestSum);
}
public static void main(String[] args) {
int[] arr = {1, 60, -10, 70, -80, 85};
findPairClosestToZero(arr);
}
}
✅ Output
For input:
{1, 60, -10, 70, -80, 85}
Output:
Pair: (-80, 85) with sum closest to zero = 5sliding window of k size
===
public class SlidingWindowExample {
// Function to find maximum sum of subarray of size k
public static int maxSumSubarray(int[] arr, int k) {
if (arr.length < k) {
System.out.println("Invalid input: window size is bigger than array length");
return -1;
}
// Step 1: Compute sum of first window
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += arr[i];
}
int maxSum = windowSum;
// Step 2: Slide the window
for (int i = k; i < arr.length; i++) {
// Remove element going out + add new element
windowSum += arr[i] - arr[i - k];
maxSum = Math.max(maxSum, windowSum);
}
return maxSum;
}
public static void main(String[] args) {
int[] arr = {2, 1, 5, 1, 3, 2};
int k = 3;
System.out.println("Maximum sum of subarray of size " + k + " = " + maxSumSubarray(arr, k));
}
}
given an int array, find occurance of each lement
=========================
import java.util.HashMap;
import java.util.Map;
public class ElementFrequency {
public static void countOccurrences(int[] arr) {
// Use HashMap to store element -> frequency
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : arr) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
// Print the occurrences
System.out.println("Element frequencies:");
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 2, 3, 1, 4, 2, 5, 3, 3};
countOccurrences(arr);
}
}
✅ Output
For input:
arr = {1, 2, 2, 3, 1, 4, 2, 5, 3, 3}
Output:
Element frequencies:
1 -> 2
2 -> 3
3 -> 3
4 -> 1
5 -> 1
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
🔎 What it does:
freqMap is a HashMap<Integer, Integer> → it maps each element to how many times it occurs.
freqMap.getOrDefault(num, 0):
Looks up the key num in the map.
If it exists, it returns the current frequency.
If it does not exist, it returns the default value 0.
+ 1: we add one occurrence for the current element.
freqMap.put(num, ...): updates the map with the new frequency.
Example Walkthrough
Say arr = {1, 2, 2}
First element = 1
Map empty → getOrDefault(1, 0) = 0
New frequency = 0 + 1 = 1
Map = {1=1}
Second element = 2
Not present → getOrDefault(2, 0) = 0
New frequency = 0 + 1 = 1
Map = {1=1, 2=1}
Third element = 2
Already present → getOrDefault(2, 0) = 1
New frequency = 1 + 1 = 2
Map = {1=1, 2=2}
✅ This is a shorthand way of saying:
if (freqMap.containsKey(num)) {
freqMap.put(num, freqMap.get(num) + 1);
} else {
freqMap.put(num, 1);
}find leader in an array
=========================
👉 Definition:An element in an array is called a leader if it is strictly greater than all elements to its right.By definition, the rightmost element is always a leader.
✅ Example
Input: arr = {16, 17, 4, 3, 5, 2}
Output: Leaders are 17, 5, 2
Start from right: 2 is a leader.
Next, 5 > 2 → leader.
Next, 3 < 5 → not leader.
Next, 4 < 5 → not leader.
Next, 17 > 5 → leader.
16 < 17 → not leader.
🔹 Efficient Java Solution (O(n) time, O(1) space)
We traverse from right to left, keeping track of the maximum so far.
import java.util.*;
public class LeadersInArray {
public static void main(String[] args) {
int[] arr = {16, 17, 4, 3, 5, 2};
findLeaders(arr);
}
static void findLeaders(int[] arr) {
int n = arr.length;
int maxFromRight = arr[n - 1]; // last element is always a leader
System.out.print("Leaders: " + maxFromRight + " ");
// Traverse from second last element backwards
for (int i = n - 2; i >= 0; i--) {
if (arr[i] > maxFromRight) {
maxFromRight = arr[i];
System.out.print(maxFromRight + " ");
}
}
}
}
🔹 Output
Leaders: 2 5 17Given an int array, check if the elements form a set of consecutive numbers (order doesn’t matter)."
=========================
✅ Example
Input: arr = {5, 3, 4, 2, 1}
Output: true (because elements are 1,2,3,4,5 which are consecutive)
Input: arr = {7, 6, 5, 9}
Output: false (because 8 is missing)
🔹 Key Idea
Find min and max.
Check if:
max - min + 1 == array length
If not → they cannot be consecutive.
Ensure there are no duplicates (otherwise they’re not consecutive).
🔹 Java Implementation
import java.util.*;
public class ConsecutiveCheck {
public static void main(String[] args) {
int[] arr1 = {5, 3, 4, 2, 1};
int[] arr2 = {7, 6, 5, 9};
System.out.println(areConsecutive(arr1)); // true
System.out.println(areConsecutive(arr2)); // false
}
static boolean areConsecutive(int[] arr) {
int n = arr.length;
int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
// Step 1: find min and max
for (int num : arr) {
min = Math.min(min, num);
max = Math.max(max, num);
}
// Step 2: quick check
if (max - min + 1 != n) return false;
// Step 3: check duplicates
Set<Integer> seen = new HashSet<>();
for (int num : arr) {
if (!seen.add(num)) return false; // duplicate found
}
return true;
}
}
🔹 Output
true
false
⚡ Efficient:
Time → O(n)
Space → O(n) (for HashSet)
==========
🔹 Idea
Pick an element → place it in current position → recurse for the rest.
Use backtracking (swap technique or visited array).
Since elements are distinct, no duplicate handling is required.
🔹 Java Solution (Backtracking with Swap)
import java.util.*;
public class Permutations {
public static void main(String[] args) {
int[] arr = {1, 2, 3};
List<List<Integer>> result = permute(arr);
for (List<Integer> perm : result) {
System.out.println(perm);
}
}
public static List<List<Integer>> permute(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
backtrack(nums, 0, res);
return res;
}
private static void backtrack(int[] nums, int start, List<List<Integer>> res) {
if (start == nums.length) {
List<Integer> perm = new ArrayList<>();
for (int num : nums) perm.add(num);
res.add(perm);
return;
}
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
backtrack(nums, start + 1, res);
swap(nums, start, i); // backtrack
}
}
private static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
🔹 Example Output for {1,2,3}
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 2, 1]
[3, 1, 2]
🔹 Complexity
Time: O(n × n!) → because there are n! permutations, and copying each permutation takes O(n).
Space: O(n) (recursion stack).
move zero element to end of array
-------
logic
---
int nz=0
int z=0
int size=a.length;
if (size==0 or size==1) return
whilee(nz]<size){
if(a[nz]!=0)}
int temp=a[nz];
a[nz]=a[z];
a[z]=temp;
nz++
z++
}else{
nz++;
}
}
find subarray of array
=====
int a[]={1,2,3}
subarray
0-0 1
0-1 1 2
0-2 1 2 3
1-1 2
1-2 2 3
2-2 3
public class SubarraysExample {
public static void printSubarrays(int[] arr) {
int n = arr.length;
// Start index
for (int i = 0; i < n; i++) {
// End index
for (int j = i; j < n; j++) {
// Print subarray from i to j
System.out.print("[");
for (int k = i; k <= j; k++) {
System.out.print(arr[k]);
if (k < j) System.out.print(", ");
}
System.out.println("]");
}
}
}
public static void main(String[] args) {
int[] arr = {1, 2, 3};
System.out.println("All Subarrays:");
printSubarrays(arr);
}
}
how to rotate array right or left by k size
=====
k= positive no mean left rotate
k=-ve no mean right rotate
logic
--
public void rotateone (int a[]){
int temp=0;
temp=a[0];
for(int i=1;i<a.length;i++){
a[i-1]=a[i];
}
a[a.length-1]=temp;
}
public void rotateArray(int b[], int k){
int k=k% a.length;
if(k<0){
k=k+a.length;
}
for(int i=1;i<k;i++){
rotateone(a,);
}
}
Comments