đź“Ś To sort an array -
Arrays.sort(arr);
Arrays.sort(arr,start_index,end_index);
đź“Ś To sort an array in reverse order -
import java.util.arrays;
import java.util.Collections;
//Code
Arrays.sort(arr, Collections.reverseOrder());
đź“ŚComparator in Java -
public int compare(Object obj1,Object obj2)
// Create a class that implements the Comparator interface -
class Temp implements Comparator<Temp> {
// Some code
// Write the logic for the compare method
// Need to be public
// Sort in ascending order
public int compare(Temp a,Temp b) {
return a.value-b.value;
}
}
// To sort the array -
Collections.sort(arr,new Temp());
// Note -
public int compare(Temp a,Temp b) {
return a.value-b.value; // Sorts in ascending order
}
public int compare(Temp a,Temp b) {
return b.value-a.value; // Sorts in desceding order
}
// Inside custom class which implements comparable
int compareTo(Temp b) {
return this.value-b.value; // Ascending
// return b.value-this.value; // Descending
}
Or you could do as -
Arrays.sort(arr, new Comparator<Object>() {
// This must be public otherwise gives an error
public int compare(Object 1, Object 2) {
// logic
}
})
Example -
public int compare(Student customer1,
Student customer2)
{
// Comparing customers
int NameCompare = customer1.getName().compareTo(
customer2.getName());
int AgeCompare = customer1.getAge().compareTo(
customer2.getAge());
// 2nd level comparison
return (NameCompare == 0) ? AgeCompare
: NameCompare;
}
Say we are given a 2D integer array and we need to sort the array in ascending order based on the second value of each row(or second element of each 1D array). One way to sort the array in Java is as follows:
Arrays.sort(arr, (a,b)-> a[1]-b[1]);
But it does not always work for all test cases generally large test cases. Because this could cause Integer Overflow.
What if the input array looks like this: [[-2147483646,-2147483645],[2147483646,2147483647]]
In that case, according to the code we are subtracting “2147483647” from “-2147483645” or -2147483645–2147483647=-4294967292; which causes integer overflow.
If we modify the above code a little bit, we can avoid integer overflow. The modified code is as follows:
Arrays.sort(arr, (a,b) -> a[1]<b[1] ? -1 : 1);
đź“ŚBinary search in Array
// Array arr needs to be sorted
// Returns index of searchKey in array
int index = Arrays.binarySearch(arr,searchKey);
đź“ŚFill the array with a value -
// By default 0 is filled
// If another value to fill
int fillValue = 1;
Arrays.fill(arrayname, fillValue);
đź“ŚMaximum sum subarray problem -
// Find the cumulative sum of the array
// To find the sum of a subarray with start index i and end index j
// It can be simply done by cumulativeSum(j)-cumulativeSum(i-1)
// Compare the sum for all possible subarrays
Another solution -
public static int getMaximumSubarraySum(int array[])
{
int max_sum=array[0];
int temp_sum=array[0];
/*Start from 1 because index 0 already included*/
for (int i=1;i<array.length;i++)
{
/*Set temp_sum to maximum of the two - array[i] and temp_sum+array[i]*/
temp_sum=max(array[i],temp_sum+array[i]);
/*Set maximum sum to maximum of the two - temp_sum and max_sum*/
max_sum=max(max_sum,temp_sum);
}
return max_sum;
}
đź“ŚMaximum product subarray problem -
public static int getMaximumSubarrayProduct(int array[])
{
int minProduct,maxProduct,result;
minProduct=array[0];
maxProduct=array[0];
result=array[0];
int a,b;
/*Start from index 1 as index 0 already considered*/
for (int i=1;i<array.length;i++)
{
a=minProduct*array[i];
b=maxProduct*array[i];
/*Also consider array[i] because it can be smaller or larger
than both a and b and we need to consider that*/
minProduct=min(array[i],a,b);
maxProduct=max(array[i],a,b);
result=max(maxProduct,result);
}
return result;
}
đź“ŚTaking character input in Java -
Scanner sc = new Scanner(System.in);
char c = sc.next().charAt(0);
đź“ŚJava range of data types -
đź“ŚType conversion in Java -
// Implicit type conversion -
// Byte -> Short -> Int -> Long -> Float -> Double
// Explicit type conversion -
// Double -> Float -> Long -> Int -> Short -> Byte
// String conversions
// String to Integer or Long or double or Boolean
int x = Integer.parseInt(str);
long y = Long.parseLong(str);
double z = Double.parseDouble(str);
boolean t = Boolean.parseBoolean(str);
// Integer to string
String str = Integer.toString(num);
String str = String.valueOf(num);
// String to character
int ch = str.charAt(0);
// String to a character array
char[] ch = str.toCharArray();
// Character array to string
String str = String.valueOf(chars);
String str = new String(chars);
// Character to int
int n = ch - '0';
// Int to character
int a = 65;
char ch = (char)a; // A
int a = 1;
char ch = (char)(a+'0'); // '1'
// Binary string to integer
String str = "10101";
int decimal = Integer.parseInt(str,2); // Parameters are string s and redix r
// Integer to the binary string
int x = 5;
String str = Integer.toBinaryString(x);
đź“ŚProgram to find GCD of two numbers -
public static long gcd(long x, long y)
{
if (y==0)
return x;
return gcd(y,x%y);
}
đź“ŚString comparison and substring in Java -
String s1,s2;
// ___code___
s1.equals(s2); // Compares if given two strings are equal and returns boolean
s1.equalsIgnoreCase(s2); // Compare strings are equal and ignoring case
s1.compareTo(s2);
// s1==s2 - returns 0
// s1>s2 - returns >0
// s1<s2 - returns <0
// Substring
s1.substring(start); // start to end of string
s1.substring(startIndex,endIndex); // [startIndex,endIndex)
đź“ŚString split -
String s = "Hello world! Good morning";
String[] words = s.split(" "); // split on the basis of delimiter operator
đź“Ś 'Character' class methods in Java -
// Use case - Character.methodName(character);
isLetter();
isDigit();
isWhitespace();
isUpperCase();
isLowerCase();
toUpperCase();
toLowerCase();
toString();
đź“Ś Collection framework -
// Basic collection functions
add(e) // add element e to collection
addAll(c) // add collection c to collection
remove(e) // remove an element e from collection
removeAll(c) // removes elements of collection c from collection
size() // returns size of collection
clear() // removes all elements from collection
contains(e) // to search an element e in collection
toArray() // converts collection to array
isEmpty() // checks if collection is empty
equals(c) // matches two collections
hashCode() // returns the hashcode of the collection
// Arraylist
ArrayList<Integer> al = new ArrayList<>();
al.add(5); // To add element
al.remove(2); // Removes element at index 2
al.remove(new Integer(2)); // Removes element 2 from arraylist
// Linked List
LinkedList<Integer> ll = new LinkedList<>();
ll.remove(); // Remove head of list
// Same add and remove functions
ll.addFirst(7); // Add element to beginning of list
ll.addLast(12); // Add element to end of list
ll.getFirst(); // Returns first element of list
ll.getLast(); // Returns last element of list
ll.pollFirst(); // Returns and removes first element of list, returns null if empty
ll.pollLast(); // Returns and removes last element of list, returns null if empty
// Vector
Vector<Integer> v = new Vector<>();
// Same add and remove functions
// Stack
Stack<Integer> s = new Stack<>();
s.push(5); // To push element to stack
s.pop(); // Pop element from stack
s.peek(); // Returns top element of stack
// Priority queue
PriorityQueue<Integer>pq = new PriorityQueue<>(); // min priority queue
pq.add(5); // Add element to priority queue
pq.peek(); // Returns min priority element without deleting it
pq.poll(); // Returns min priority element and also deletes it
// Max priority queue
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
// Custom priority-based priority queue
PriorityQueue<Object> heapLow = new PriorityQueue<>(new Comparator<Object>() {
int compare(Object lhs, Object rhs) {
// Logic
}
});
// Hashset - Values can't be repeated
HashSet<Integer>hs = new HashSet<>();
hs.add(5); // Adding elements to hash
// Similarly, LinkedHashSet and TreeSet
// HashMap
HashMap<Integer,String>hm = new HashMap<>();
hm.put(74,"Meet"); // Add elements to hash map
hm.get(74); // Get value for the key
hm.getOrDefault(14,"Meet"); // Get value for key if exists otherwise default value is returned
// Iterating in a hashmap
for (Map.Entry<Integer,String>e : hm.entrySet())
System.out.println(e.getKey()+":"+e.getValue());
// TreeMap
// HashMap gives an unordered list. If you want ordering based on the keys,use TreeMap
TreeMap<Integer,String>tm = new TreeMap<>();
int k = 5;
tm.ceilingEntry(k); // Returns Map.Entry with least entry greater than or equal to key
tm.ceilingKey(k); // Returns key with least value greater than or equal to key
tm.floorEntry(k); // Returns Map.Entry with greatest entry less than or equal to key
tm.floorKey(k); // Returns key with greatest entry less than or equal to key
tm.firstKey(); tm.firstEntry(); // Returns first key/entry of map
tm.lastKey(); tm.lastEntry(); // Returns last key/entry of map
tm.higherKey(k); tm.higherEntry(k); // Returns least entry/key strictly greater than key
tm.lowerKey(k); tm.lowerEntry(k); // Returns greatest entry/key strictly less than key
// Returns null for all above cases if no result exists
// Deque
Deque<Integer> dq=new ArrayDeque<>();
dq.add(7); // Add to tail of queue
dq.addFirst(7); // Add to tail of queue
dq.addLast(7); // Add to tail of queue
dq.peek(); // Retrieve element at head of queue
dq.peekFirst(); // Retrieve element at head of queue
dq.peekLast(); // Retrieve element at tail of queue
dq.poll(); // Remove element at head of queue
dq.pollFirst(); // Remove element at head of queue
dq.pollLast(); // Remove element at tail of queue
// To implement stack using deque
dq.push(7); // Push element to head of queue
dq.pop(); // Pop element from head of queue
// Priority Queue for custom class object
class Interval implements Comparable<Interval> {
// Class properties here
int start;
int end;
// Overrirde the compareTo method
public int compareTo(Interval x) {
int diffStart = this.start-x.start;
int diffEnd = this.end-x.end;
return diffStart!=0 ? diffStart : diffEnd;
}
}
// And instantiating it like this -
PriorityQueue<Interval> pq = new PriorityQueue<>();
// Iterators
Iterator itr = al.iterator(); // Say al collection is arraylist
// Iterating over arraylist now
while (itr.hasNext()) {
int x = (Integer)itr.next();
System.out.println(x);
}
đź“ŚNext permutation problem in Java
// The next permutation of an array of integers is the next lexicographically greater permutation of its integer.
// For example, the next permutation of arr = [1,2,3] is [1,3,2].
// While the next permutation of arr = [3,2,1] is [1,2,3] because [3,2,1] does not have a lexicographical larger rearrangement.
class Solution {
public void nextPermutation(int[] nums) {
int temp;
int index=nums.length-1;
while (index>0 && nums[index]<=nums[index-1])
index--;
index=index-1; //Index is -1 in case of descending order array
if (index>=0) {
int j=nums.length-1;
while (nums[index]>=nums[j])
j--;
swap(nums,index,j);
}
// Reverse array after index i.e index+1
int start=index+1;
int end=nums.length-1;
while (start<end)
swap(nums,start++,end--);
}
public void swap(int nums[],int x,int y) {
int temp=nums[x];
nums[x]=nums[y];
nums[y]=temp;
}
}
đź“ŚPair in Java
// Import this package first
import javafx.util.Pair;
Pair<Integer, String> p = new Pair<>(74,"Meet");
p.getKey(); // Returns 74
p.getValue(); // Returns Meet
Notes on Binary search
int low = 0;
int high = arr.length-1;
while(low<=high) {
if (arr[mid]==key)
return mid;
else if (arr[mid]>key)
high=mid-1;
else
low=mid+1;
}
// Note that
// If the key exists, returns from mid
// If the key do not exists, the loop terminates and
// low stores element just greater than key
// high stores element just smaller than key
Â