Java DSA Cheatsheet (Easy–Medium) — Quick Revision
For online assessments (Aptitude + Domain + Hands-on Coding). Language: Java.
1) Fast I/O (Most Used)
import [Link].*;
import [Link].*;
class FastScanner {
BufferedReader br = new BufferedReader(new InputStreamReader([Link]));
StringTokenizer st;
String next() throws IOException {
while (st == null || ![Link]())
st = new StringTokenizer([Link]());
return [Link]();
}
int nextInt() throws IOException { return [Link](next()); }
long nextLong() throws IOException { return [Link](next()); }
double nextDouble() throws IOException { return [Link](next()); }
}
// Print fast
StringBuilder sb = new StringBuilder();
[Link](ans).append('\n');
[Link]([Link]());
2) Arrays & Sorting
int[] a = {5, 2, 9};
[Link](a); // ascending
Integer[] b = {5, 2, 9};
[Link](b, [Link]()); // descending
// Reverse array
for(int l=0, r=[Link]-1; l<r; l++, r--){
int t=a[l]; a[l]=a[r]; a[r]=t;
}
3) HashMap / HashSet (Frequency, Two Sum)
HashMap<Integer,Integer> map = new HashMap<>();
for(int x: a) [Link](x, [Link](x,0)+1);
HashSet<Integer> set = new HashSet<>();
[Link](x);
if([Link](x)) { /* ... */ }
// Two Sum indices
int[] twoSum(int[] arr, int target){
HashMap<Integer,Integer> pos = new HashMap<>();
for(int i=0;i<[Link];i++){
int need = target - arr[i];
if([Link](need)) return new int[]{[Link](need), i};
[Link](arr[i], i);
}
return new int[]{-1,-1};
}
4) Prefix Sum + Subarray Sum = K
long[] pref = new long[n+1];
for(int i=0;i<n;i++) pref[i+1] = pref[i] + a[i];
// sum l..r = pref[r+1] - pref[l]
// Count subarrays with sum = k (works with negatives too)
long countSubarraysK(int[] a, long k){
HashMap<Long,Integer> hm = new HashMap<>();
[Link](0L, 1);
long sum=0, ans=0;
for(int x: a){
sum += x;
ans += [Link](sum-k, 0);
[Link](sum, [Link](sum,0)+1);
}
return ans;
}
5) Two Pointers + Sliding Window
// Two pointers (sorted arrays / pair sum)
int l=0, r=n-1;
while(l<r){
long s = a[l] + a[r];
if(s==target) break;
else if(s<target) l++;
else r--;
}
// Sliding window for non-negative arrays: longest sum <= K
int i=0; long sum=0; int best=0;
for(int j=0;j<n;j++){
sum += a[j];
while(i<=j && sum>k){ sum -= a[i++]; }
best = [Link](best, j-i+1);
}
6) Kadane (Max Subarray Sum)
long maxSubarraySum(int[] a){
long cur=0, best=Long.MIN_VALUE;
for(int x: a){
cur = [Link]((long)x, cur + x);
best = [Link](best, cur);
}
return best;
}
7) Binary Search (Classic)
int binarySearch(int[] a, int x){
int lo=0, hi=[Link]-1;
while(lo<=hi){
int mid = lo + (hi-lo)/2;
if(a[mid]==x) return mid;
else if(a[mid]<x) lo=mid+1;
else hi=mid-1;
}
return -1;
}
8) Stack / Deque / PriorityQueue
// Stack
Stack<Integer> st = new Stack<>();
[Link](10); [Link](); [Link]();
// Deque (best for sliding window max)
Deque<Integer> dq = new ArrayDeque<>();
[Link](1); [Link]();
// PriorityQueue
PriorityQueue<Integer> pq = new PriorityQueue<>(); // min-heap
PriorityQueue<Integer> maxpq = new PriorityQueue<>([Link]());
9) GCD / LCM + Mod
static long gcd(long a, long b){
while(b!=0){ long t=a%b; a=b; b=t; }
return a;
}
static long lcm(long a, long b){
return (a / gcd(a,b)) * b;
}
static final long MOD = 1000000007L;
ans = (ans % MOD + MOD) % MOD;
10) Strings Quick Ops
String s = "abc";
char ch = [Link](0);
String sub = [Link](1, 3); // [1,3)
// Reverse string
char[] arr = [Link]();
for(int l=0,r=[Link]-1; l<r; l++,r--){
char t=arr[l]; arr[l]=arr[r]; arr[r]=t;
}
String rev = new String(arr);
// Character helpers
[Link](ch);
[Link](ch);
[Link](ch);
11) Common Patterns to Practice
• Arrays: two sum, rotate by K, remove duplicates, move zeros, missing number, max subarray
(Kadane).
• Strings: palindrome, anagram, first non-repeating char, valid parentheses, word count, longest
word.
• Hashing: frequency map, subarray sum = K, longest consecutive sequence, majority element.
• Stack/Deque: next greater element, stock span, sliding window maximum.
12) Always Remember
• Use long for sums/prefix sums and multiplications.
• When input constraints are big, avoid O(n^2). Prefer hashing / sorting / two pointers.
• In contests: handle edge cases (n=0/1, negatives, duplicates).
• Write clean methods + avoid extra prints.