public class PrintPermutations {
public static void main(String[] args) {
String str = "abc";
printPermutations(str, "");
}
public static void printPermutations(String str, String asf) {
if (str.length() == 0) {
System.out.println(asf);
return;
}
for (int i = 0; i < str.length(); i++) {
char ch = str.charAt(i);
String rem = str.substring(0, i) + str.substring(i + 1, str.length() );
printPermutations(rem, asf + ch);
}
}
}
public class PrintMazePathWithMultipleJumps {
public static void main(String[] args) throws Exception {
printMazePaths(0, 0, 2, 2, "");
}
// sr - source row
// sc - source column
// dr - destination row
// dc - destination column
public static void printMazePaths(int sr, int sc, int dr, int dc, String psf) {
if (sr == dr && sc == dc) {
System.out.println(psf);
return;
}
// horizontal
for (int jump = 1; jump <= dc - sc; jump++) {
printMazePaths(sr, sc + jump, dr, dc, psf + "h" + jump);
}
// vertical
for (int jump = 1; jump <= dr - sr; jump++) {
printMazePaths(sr + jump, sc, dr, dc, psf + "v" + jump);
}
for (int jump = 1; jump <= dc - sc && jump <= dr - sr; jump++) {
printMazePaths(sr + jump, sc + jump, dr, dc, psf + "d" + jump);
}
}
}
public class PrintMazePaths {
public static void main(String[] args) throws Exception {
printMazePaths(0, 0, 2, 2, "");
}
// sr - source row
// sc - source column
// dr - destination row
// dc - destination column
public static void printMazePaths(int sr, int sc, int dr, int dc, String psf) {
if (sr == dr && sc == dc) {
System.out.println(psf);
return;
}
if (sr < dr)
printMazePaths(sr + 1, sc, dr, dc, psf + "v");
if (sc < dc)
printMazePaths(sr, sc + 1, dr, dc, psf + "h");
}
}
I/P: 3
O/P: [111, 12, 21, 3]
public class PrintStairPaths {
public static void main(String[] args) {
int n = 3;
printStairPaths(n, "");
}
public static void printStairPaths(int n, String ans) {
if (n == 0) {
System.out.println(ans);
return;
} else if (n < 0) {
return;
}
printStairPaths(n - 1, ans + "1");
printStairPaths(n - 2, ans + "2");
printStairPaths(n - 3, ans + "3");
}
}
public class Print_KPC {
static String[] codes = {".;", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tu", "vwx", "yz"};
public static void main(String[] args) {
String str = "678";
printKPC(str, "");
}
private static void printKPC(String str, String ans) {
if (str.length() == 0) {
System.out.println(ans);
return;
}
char ch = str.charAt(0);
int num1 = ch - '0';
String num1_code = codes[num1];
for (int i = 0; i < num1_code.length(); i++)
printKPC(str.substring(1), ans + num1_code.charAt(i));
}
}
package pep.Day10;
public class
Print_Subsequence {
public static void main(String[] args) {
String str = "abc";
printSubsequence(str, "");
}
private static void printSubsequence(String str, String ans) {
if (str.length() == 0) {
System.out.println(ans);
return;
}
printSubsequence(str.substring(1), ans + "");
printSubsequence(str.substring(1), ans + str.charAt(0));
}
}
- - -
- - 3
- 2 -
- 2 3
1 - -
1 - 3
1 2 -
1 2 3
package jan20;
public class AllSubsetArray {
public static void main(String[] args) {
// TC: O(1), SC: O(1)
char[] arr = {'a', 'b', 'c'}; // Input array of length n = 3
// TC: O(1), SC: O(1)
int limit = (int) Math.pow(2, arr.length); // Total subsets = 2^n
// TC: Outer loop runs 2^n times => O(2^n), SC: O(1)
for (int i = 0; i < limit; i++) {
// TC: O(1), SC: O(n) — ans string can grow up to length n
String ans = "";
// TC: O(1), SC: O(1)
int temp = i;
// TC: Inner loop runs n times => O(n), SC: O(1)
for (int j = arr.length - 1; j >= 0; j--) {
// TC: O(1), SC: O(1)
int remainder = temp % 2;
// TC: O(1), SC: O(1)
temp = temp / 2;
// TC: O(1) string concat, SC: O(n) over all iterations
if (remainder == 0)
ans = "- " + ans;
else
ans = arr[j] + " " + ans;
}
// TC: O(1), SC: O(1)
System.out.println(ans); // Print one subset
}
}
}
📊 Complexity Table
Case Time Complexity Space Complexity Explanation Best O(2ⁿ × n) O(n) Even in best case, the outer loop runs 2ⁿ times, and inner loop n times. Average O(2ⁿ × n) O(n) Same work regardless of actual input content. Worst O(2ⁿ × n) O(n) Full 2ⁿ iterations with O(n) string operations in each.
I/P: {10,20,30}
O/P:
10 10 20 10 20 30 20 20 30 30
package jan20;
public class SubArray {
public static void main(String[] args) {
int[] arr = {10, 20, 30}; // O(1) time, O(1) space (static array initialization)
for (int i = 0; i < arr.length; i++) { // Outer loop: O(n)
for (int j = i; j < arr.length; j++) { // Middle loop: O(n)
for (int k = i; k <= j; k++) { // Inner loop: O(n)
System.out.print(arr[k] + " "); // O(1) time (printing element)
}
System.out.println(); // O(1) time (printing new line)
}
}
}
}
| Case | Time Complexity | Space Complexity | Explanation |
|---|---|---|---|
| Best Case | O(n³) | O(1) | Even if array is small, still tries all subarrays, 3 nested loops. |
| Average Case | O(n³) | O(1) | Same nested structure always. |
| Worst Case | O(n³) | O(1) | Largest input → all three loops fully expand to n iterations. |
✅ 1-line Summary:
package jan20;
public class InverseArray {
public static void main(String[] args) {
// Create and initialize the input array
// Time Complexity: O(1)
// Space Complexity: O(n) – storing input array of size n
int[] arr = new int[]{4, 0, 2, 3, 1};
// Create an output array to store the inverse
// Time Complexity: O(1)
// Space Complexity: O(n) – storing the result of inversion
int[] ans = new int[arr.length];
// Loop through the input array
// Time Complexity: O(n) – loop runs n times
// Space Complexity: O(1) – constant space used in loop
for (int i = 0; i < arr.length; i++) {
int index = arr[i]; // O(1)
ans[index] = i; // O(1)
}
// Print the inverse array
// Time Complexity: O(n) – printing all n elements
// Space Complexity: O(1)
for (int x : ans)
System.out.print(x + "\t");
}
}
| Case | Time Complexity | Explanation |
|---|---|---|
| Best Case | O(n) | Every element is processed once. |
| Average Case | O(n) | All elements are traversed and reassigned. |
| Worst Case | O(n) | Even if the array is in reverse or random order, all n elements are still processed once. |
package jan20;
public class RotateArray {
public static void main(String[] args) {
// Initialize array and rotation value
// Time: O(1), Space: O(1)
int[] arr = {2, 1, 6, 5, 4, 3};
int k = 4;
int len = arr.length;
// Adjust k if it's greater than length
// Time: O(1), Space: O(1)
k = k > len ? k % len : k;
// Adjust k if negative
// Time: O(1), Space: O(1)
k = k < 0 ? k + len : k;
// Reverse first part of array
// reverseArray is O(n) where n = len - k
reverseArray(arr, 0, len - k - 1);
// Reverse second part of array
// reverseArray is O(k)
reverseArray(arr, len - k, len - 1);
// Reverse whole array
// reverseArray is O(n)
reverseArray(arr, 0, len - 1);
// Print array
// printArray is O(n)
printArray(arr);
}
private static void reverseArray(int[] arr, int left, int right) {
// Reversing by swapping
// Time: O(right - left + 1), Space: O(1) (in-place)
while (left < right) {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
left++;
right--;
}
}
private static void printArray(int[] arr) {
// Loop through array
// Time: O(n), Space: O(1)
for (int i : arr)
System.out.print(i + " ");
}
}
Final Overall:
Operation Time Complexity Space Complexity Rotate array (including 3 reversals) O(n) O(1) Print array O(n) O(1) 🔥 Total: O(n) time and O(1) space! Very efficient because everything is done in-place!
| Case | Time Complexity | Space Complexity | Explanation |
|---|---|---|---|
| Best Case | O(n) | O(1) | Even if no actual rotation is needed (k = 0 or k = n), still needs 3 full array reversals. |
| Average Case | O(n) | O(1) | Typically for any k, we reverse parts and whole array → linear time. |
| Worst Case | O(n) | O(1) | When k is very large (e.g., much bigger than n) — we still normalize k and do 3 reversals on the array. |
package jan20;
import java.util.Scanner;
public class SumOf2Arrays {
public static void main(String[] args) {
// Create a Scanner object for input
// TC: O(1), SC: O(1)
Scanner sc = new Scanner(System.in);
int size1 = sc.nextInt();
// TC: O(1), SC: O(1)
int[] arr1 = new int[size1];
// TC: O(1), SC: O(size1)
for (int i = 0; i < size1; i++) {
arr1[i] = sc.nextInt();
// TC: O(size1), SC: O(1) per element (already allocated)
}
int size2 = sc.nextInt();
// TC: O(1), SC: O(1)
int[] arr2 = new int[size2];
// TC: O(1), SC: O(size2)
for (int i = 0; i < size2; i++) {
arr2[i] = sc.nextInt();
// TC: O(size2), SC: O(1) per element (already allocated)
}
sum(arr1, size1, arr2, size2);
// TC: O(max(size1, size2)), SC: O(max(size1, size2))
}
private static void sum(int[] arr1, int size1, int[] arr2, int size2) {
int p1 = size1 - 1, p2 = size2 - 1, p3, carry = 0;
// TC: O(1), SC: O(1)
int[] ansArr = new int[size1 > size2 ? size1 + 1 : size2 + 1];
// TC: O(1), SC: O(max(size1, size2) + 1)
p3 = ansArr.length - 1;
// TC: O(1), SC: O(1)
while (p3 > 0) {
// Loop runs O(max(size1, size2)) times
int sum = (p1 >= 0 ? arr1[p1] : 0) + (p2 >= 0 ? arr2[p2] : 0) + carry;
// TC: O(1), SC: O(1)
ansArr[p3] = sum % 10;
// TC: O(1), SC: O(1)
carry = sum / 10;
// TC: O(1), SC: O(1)
p1--;
p2--;
p3--;
// TC: O(1) each
}
if (carry > 0) ansArr[p3] = carry;
// TC: O(1), SC: O(1)
for (int i : ansArr){
System.out.print(i + "");
// TC: O(max(size1, size2)), SC: O(1) per element print
}
}
}
| Case | Time Complexity | Space Complexity | 1-line Explanation |
|---|---|---|---|
| Best Case | O(max(size1, size2)) | O(max(size1, size2)) | Always need to add all digits even if one array has mostly zeros. |
| Average Case | O(max(size1, size2)) | O(max(size1, size2)) | Typically process all digits with some carries happening. |
| Worst Case | O(max(size1, size2)) | O(max(size1, size2)) | Maximum possible carries (like 999 + 1) but still proportional to number of digits. |
✅ Summary in simple words:
Time always depends on the larger array size, because addition needs to touch every digit once.
Space always depends on the size of the bigger array +1 (for possible carry at the most significant digit).
package jan19;
import java.util.Scanner;
public class BarChart {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// Time Complexity: O(1), initializing the scanner takes constant time.
// Space Complexity: O(1), using a constant amount of space for the scanner object.
int n = scanner.nextInt();
// Time Complexity: O(1), reading a single integer.
// Space Complexity: O(1), storing a single integer.
int[] arr = new int[n];
// Time Complexity: O(1), declaring the array.
// Space Complexity: O(n), an array of size n is created.
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
// Time Complexity: O(n), iterates over the array to input n elements.
// Space Complexity: O(n), storing n integers in the array.
int max = findMaxValue(arr);
// Time Complexity: O(n), calling findMaxValue, which iterates over the array once.
// Space Complexity: O(1), storing the maximum value (single integer).
for (int i = max; i > 0; i--) {
for (int j = 0; j < n; j++) {
if (i <= arr[j]) System.out.print(" * ");
else System.out.print(" ");
}
System.out.println();
}
// Time Complexity: O(n * max), The outer loop runs 'max' times and the inner loop runs 'n' times.
// Space Complexity: O(1), only printing and no additional space is used apart from loop variables.
}
public static int findMaxValue(int[] arr) {
int max = arr[0];
// Time Complexity: O(1), initialization takes constant time.
// Space Complexity: O(1), storing a single value.
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// Time Complexity: O(n), iterating through the array once to find the maximum value.
// Space Complexity: O(1), only storing a single integer for the max value.
}
/*
Case Time Complexity (TC) Space Complexity (SC)
Best Case O(n * max) O(n)
Average Case O(n * max) O(n)
Worst Case O(n * max) O(n)
*/
public class anyBaseToAnyBase {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num = sc.nextInt(); // O(1) - Read input number
int sourceBase = sc.nextInt(); // O(1) - Read source base
int finalBase = sc.nextInt(); // O(1) - Read final base
int val = numToBase(num, sourceBase); // O(log_sourceBase n) - Convert to decimal
baseToNum(val, finalBase); // O(log_finalBase val) - Convert to final base
}
public static int numToBase(int num, int sourceBase) {
int ans = 0;
int idx = 0;
while (num > 0) { // O(log_sourceBase n) - Loop iterates based on number of digits in base-sourceBase
int rem = num % 10; // O(1) - Extract last digit (assuming base 10 input)
ans += (int) Math.pow(sourceBase, idx++) * rem; // O(1) - Calculate decimal equivalent (assuming constant-time Math.pow)
num /= 10; // O(1) - Remove last digit
}
return ans;
}
public static void baseToNum(int num, int finalBase) {
int ans = 0;
int idx = 0;
while (num > 0) { // O(log_finalBase val) - Loop iterates based on number of digits in base-finalBase
int rem = num % finalBase; // O(1) - Extract last digit (assuming base-finalBase)
ans += (int) Math.pow(10, idx++) * rem; // O(1) - Calculate final base equivalent (assuming constant-time Math.pow)
num /= finalBase; // O(1) - Remove last digit
}
System.out.println(ans);
}
}
Time Complexity:The time complexity analysis is based on the number of iterations required in the two conversion loops. The number of iterations in each loop depends on the number of digits in the corresponding base.1. Best Case: O(log min(sourceBase, finalBase)) - When the input number has a small number of digits in both bases.In the best case, both bases have a small number of digits, resulting in fewer iterations.2. Worst Case: O(log max(sourceBase, finalBase)) - When the input number has a large number of digits in either base.
In the worst case, one or both bases have a large number of digits, leading to more iterations.3. Average Case: O(log avg(sourceBase, finalBase)) - Assuming a random distribution of input numbers and bases.The average case time complexity is between the best and worst case, depending on the distribution of input numbers and bases.
Space Complexity:
All Cases: O(1) - The space complexity remains constant as the code uses a
constant amount of additional space for variables regardless of the input size.
Overall:
- The anyBaseToAnyBase class has a time complexity that is generally efficient,
especially for smaller numbers and bases.
- The space complexity remains constant, making it suitable for most use cases.
package jan19;
import java.util.Scanner;
public class DecimalToAnyBase {
public static void main(String[] args) {
// Create a Scanner object for input
// Time Complexity: O(1), Space Complexity: O(1)
Scanner sc = new Scanner(System.in);
// Read the number from user
// Time Complexity: O(1)
int num = sc.nextInt();
// Read the base from user
// Time Complexity: O(1)
int base = sc.nextInt();
}
// Case Time Complexity Space Complexity
// Best Case O(log₍base₎n) O(1)
// Average Case O(log₍base₎n) O(1)
// Worst Case O(log₍base₎n) O(1)
public void method1(int num, int base) {
// Initialize answer
// Time Complexity: O(1), Space Complexity: O(1)
int ans = 0;
// Initialize position counter
// Time Complexity: O(1), Space Complexity: O(1)
int i = 0;
// Loop until number becomes 0
// Time Complexity: O(log₍base₎n)
// because in every iteration, 'num' reduces by a factor of 'base'.
while (num > 0) {
// Find remainder when divided by base
// Time Complexity: O(1)
int remainder = num % base;
// Find quotient after division by base
// Time Complexity: O(1)
int divisor = num / base;
// Update the answer
// Time Complexity: O(log log n) (for Math.pow, very small and almost constant)
ans += (int) Math.pow(10, i++) * remainder;
// Update num to be divisor
// Time Complexity: O(1)
num = divisor;
}
// Print the final answer
// Time Complexity: O(1)
System.out.println(ans);
}
// Case Time Complexity Space Complexity
// Best Case O(log₍base₎n) O(1)
// Average Case O(log₍base₎n) O(1)
// Worst Case O(log₍base₎n) O(1)
// Same big O, but much faster in practice.
public void method2(int num, int base) {
int ans = 0; // O(1)
int multiplier = 1; // Instead of using Math.pow()
while (num > 0) { // O(log₍base₎n)
int remainder = num % base; // O(1)
ans += remainder * multiplier; // O(1)
num = num / base; // O(1)
multiplier *= 10; // O(1) -> simply multiplying by 10 each time
}
System.out.println(ans); // O(1)
}
/*
Why is multiplier *= 10 better than Math.pow(10, i++)?
Because:
*** multiplier *= 10 ➔ simple integer multiplication → very fast (O(1))
*** Math.pow() ➔ uses internal floating point operations → slower, even if small.
*/
}
eg. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 Output: 1 6 11 16 2 7 12 3 8 4 Approach:...
