Java Syntax

Table of contents

  • One, Two, and Three-dimensional array
int[] result = new int[list.size()];
int[][] twoD_arr = new int[10][20];
int[][][] threeD_arr = new int[10][20][30];
int[] intCode = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
int[][] DIRECTIONS = { {1,0}, {-1,0}, {0,1}, {0,-1} };
//initialize 2-d array
ans[i / 3] = new int[] { nums[i], nums[i + 1], nums[i + 2] };

//intialize array alongwith variables
int n=obstacles.length, length=0, res[]=new int[n], lis[]=new int[n];

Array useful method

//it will compare the contents of two arrays and return true if it is equal or false otherwise
Arrays.equals(grid[i],grid[0]) 

//return array of size 0
//it makes sense we are creating an array of size 0.
return new int[0];

//return a new array
return new int[] {map.get(diff),i};

//It copies the specified array, truncating or padding with false
//(if necessary) so the copy has the specified length. 
int[] orderHeight = Arrays.copyOf(height, n);


//it will return a copy of array between start and end index
return Arrays.copyOfRange(intervals, 0, index+1);

//array length
int m = matrix.length

Sorting Array

//sort the array based on column, object type
//for primitive type you need to convert array into list
Arrays.sort(queries,(a,b)->(a[2]-b[2]));

//ref - 452. Minimum Number of Arrows to Burst Balloons
//sort for int out of bounds nos
Arrays.sort(points, (a, b) -> {
    if (a[1] < b[1])
        return -1;
    if (a[1] > b[1])
        return 1;
    return 0;
});
  • If the end point of interval a (a[1]) is less than the end point of interval b (b[1]), return -1. This means that a should be placed before b in the sorted array.

  • If the end point of interval a (a[1]) is greater than the end point of interval b (b[1]), return 1. This means that b should be placed before a in the sorted array.

  • If the endpoints of both intervals are equal, return 0. This means that the order of a and b doesn't matter, and they can be considered equal in terms of sorting.

Convert array to list

Arrays asList()

else if(!Arrays.asList("",".","..").contains(t))
                        stack.push(t);

// Getting the list view of Array
     List<String> list = Arrays.asList(a);

//convert two no to array then convert to list and add in list
              if(j-i+1>=3)
               ans.add(Arrays.asList(new Integer[]{i, j}));

Parsing Array or list

//Parse one dimensional 
 for(int num: list)
            result[k++] = num;

//Parse two dimensional
for(int[] num: list) 
        result[k++] = num;
  • to access a particular character
array[index]

to get a range of array

//it will return a copy of array between start and end index
return Arrays.copyOfRange(intervals, 0, index+1);

Character

useful methods

//to read character from string
s.charAt(index);

//It will check if the char is a letter or digit
Character.isLetterOrDigit

//it will convert char to lower case
Character.toLowerCase

//to check digit
boolean isDigit1 = Character.isDigit(main1.charAt(0));
or
 if(c>='0' && c<='9')

//to check letter
isLetter(char ch)

//convert to string
toString()
toString(char ch)

//convert int to character
result[i] = (char)('a'+val-1);

//convert char to int
charCode += (int) t.charAt(i);

Java Character class

String and char array

String[] myStringArray = new String[3];
char[] JavaCharArray = new char[5];

//convert string to char array
char[] charArray = word.toCharArray();

//convert char array to string
String newWord=new String(charArray);

//traversing string by converting to char array
for(Character letter: word.toCharArray())

//convert string to string array
String[] list = path.split("/");

//split with special chars
    here it will split the string with all chars placed between brackets.
    String[] terms = input.split("[\\s@&.?$+-]+");

String[] code = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};

//convert string to int
 stack.push(Integer.valueOf(op));
Integer val3 = Integer.valueOf("1010", 2); //10

//convert char to int
//you can use subtraction to convert char to int whether it is 
//for alphabet or no
System.out.println('e'-'a'); //4
System.out.println('5'-'0'); //5
System.out.println('7'-'0'); //7

//compare two strings
//you can use "==" but it checks if both objects have the same main memory location which can give errors.
//it will compare the contents of two string objects
op.equals("C")

Strings

  • Strings are immutable in java. If you want to append a character use StringBuilder or allocate new memory for a new string with appended character.

Strings useful methods

//Length of string
s.length();

//particular character in the string
s.charAt(index);

//find index
strs[index].indexOf(strs[0])!=0

//find substring
strs[0] = strs[0].substring(0, strs[0].length()-1);

//convert string to int
int hits = Integer.parseInt(string);
Integer.valueOf(s)

//It checks the equality of string with the given object.
//boolean equals(Object another)
//path.equals("/")

//sort the string
//convert string to array then sort the array
//convert sorted array to string
    char[] chars = word.toCharArray();
    Arrays.sort(chars);
    String sortedWord = new String(chars);           


//convert string to charArray
for(char c: searchWord.toCharArray())

//parse the string
for(char c: searchWord.toCharArray())
or
for(int i=0; i<s.length();i++)
 s.charAt(index);

//check whether string contains a particular string
 if(!"+-*/".contains(token))

//convert array to string
//here s1 is char array
return new String(s1);

//convert char to string
    c+""
    Character.toString(c)

//check if string is empty
    s.isEmpty()

//sort the string lexicographicaly using minHeap
    //332. Reconstruct Itinerary
 String gfg1 = String.join(" < ", "Four", "Five", "Six", "Seven");
 System.out.println(gfg1);
// Four < Five < Six < Seven

String[] str = {"a","b","c"};
System.out.println(String.join(" ",str));
//a b c

StringBuilder

  • In this, you can append a character.
StringBuilder cur = new StringBuilder();
cur.append(count).append(res.charAt(index));
res = cur.toString();

//delete char at particular index to create new string
StringBuilder current = new StringBuilder(word);
String next = current.deleteCharAt(i).toString();

//reverse the stringbuilder
return result.reverse().toString();

//add object at particular position
//object can be string, char, int etc.
StringBuilder res = new StringBuilder();
res.insert(0,dir.pop()).insert(0,"/");

Sort the array

  • Note: There is a slight difference between Arrays.sort() vs Collections.sort(). Arrays.sort works for arrays which can be of primitive data type also. Collections.sort() works for objects Collections like ArrayList, LinkedList, etc.

Arrays.sort()

Arrays.sort(nums);

//sort array of strings based on length
Arrays.sort(words, (a,b)->a.length()-b.length());

Sort the two-dimensional array

  • We will just add a comparator for ascending and descending order. Comparator is a simple and most important topic. if a-b is -1 then leave it as it is. If it is 1 then reverse it. In compare func we return 1 if a>b. Here we have used shortcut a-b. Usually, it uses quicksort at the backend which takes nlogn time but whatever algo it uses, it will take two nos at a time to compare. The comparator was demystified finally :P. 0 will not do anything.
//for ascending order
Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
//output
[[1,4],[4,5]]

// Sort by ascending starting point
Arrays.sort(intervals, (i1, i2) -> Integer.compare(i1[0], i2[0]));


//for descending order
Arrays.sort(intervals, (a,b) -> b[0] - a[0]);
//output
[[4,5],[1,4]]

to fill the array with a particular value

Arrays.fill(lis,1);

Collections

Collections important methods

Iterator

  • It is an object that can be used to loop through collections. like - ArrayList, HashSet.

  • If we try to remove items from the collection using for or for-each loop, it will result in an error BCS collection is changing size at the same time we are looping.

// Make a collection
ArrayList<String> cars = new ArrayList<String>();
cars.add("Volvo");
cars.add("BMW");
cars.add("Ford");
cars.add("Mazda");

// Get the iterator
Iterator<String> it = cars.iterator();

// Loop through a collection
while(it.hasNext()) {
  System.out.println(it.next());
}

res -> Volvo
BMW
Ford
Mazda

//remove operation
Integer i = it.next();
if(i < 10) {
it.remove();
}

remove

  • It is used to remove elements from collections through objects

  • However, in a list, it is used to remove elements through the index and object both.

  • remove(Object o), remove(int index)

  • That means that list.remove(1) removes the object at position 1 and remove(new Integer(1)) removes the first occurrence of the specified element from this list.

  • The remove method returns true if an object passed as a parameter is removed from the list. Otherwise, it returns false.

  • The remove method returns the removed element if an index is passed

  • It throws IndexOutOfBoundsException if the specified index is not in range.

  • TC - O(n)


Equals

  • It is used to compare two objects
List<Integer> leaves1 = new ArrayList();
return leaves1.equals(leaves2);
It will return true if both objects are equal
  • "==" operator is a binary equality operator used to compare primitive types like - int, short, long etc.
if (firstStudent.getScore() == 100)

Initialize collections

  • We can initialize collections with some default value ie list while defining them using the Arrays.asList method.
//template 1
HashSet<Character> set = new HashSet(Arrays.asList('a', 'e', 'i', 'o', 'u',
                'A', 'E', 'I', 'O', 'U'));
//template 2
return count.size() == new HashSet(count.values()).size();

ArrayList

  • It is dynamic in nature which means you can add nos to it dynamically.

  • ArrayList in Java

//to declare List
List<Integer> list = new ArrayList();

//access [i][j] element in list
r.get(i).get(j)

//to find list size
list.size()

//reverse list
//it will reverse the original value
Collections.reverse(level);

//declare list of 1d array
List<int[]> ans = new ArrayList();

//add 1d elements to list
ans.add(new int[] {mS,mE});

//to add an array in list
output_arr.add(Arrays.asList(nums[index],nums[low],nums[high]));
[[1,2,3],[4,5,6]]

//you can parse list same as an array, just take care of data type
    for (List<String> ticket : tickets)
    targets.computeIfAbsent(ticket.get(0), k -> new PriorityQueue()).add(ticket.get(1));

//sort list
//it will sort the original value
Collections.sort(level);
//sort and reverse
Collections.sort(values, Collections.reverseOrder());

//sublist
productsList.subList(start,end); end is not included.

//This method is used to insert a specific element at one particular position index in a list.
//it will shift the rest of the elements
add(int index, Object element)

//it will always add object at 0 index.
// first object added will be at last.
 while(!pq.isEmpty())
            result.add(0, pq.poll());

//This method is used to append a specific element to the end of a list.
add(Object o)

// this method takes an index and the updated element which needs to be inserted at that index. 
al.set(1, "For");


//add list to list of list
result.add(new ArrayList(path));

//list of list
List<List<Integer>> result = new ArrayList();
//removes no at index 1.
 al.remove(1);
//removes no 1.
 al.remove(new Integer(1));

to convert list to int array

//First method
int[] result = new int[list.size()];
     for(int num: list)
            result[k++] = num;

//Second method
int[] resArr = new int[res.size()];

for(int index=0; index<res.size(); index++) {
     resArr[index] = res.get(index);    
   } 

//Third method
//here we have converted list containing 1d array elements of size 2 to array
return ans.toArray(new int[ans.size()][2]);

//Fourth method (working one)
    //Introduced in Java 8, Stream API is used to process collections of objects. 
    //A stream is a sequence of objects that supports various
     //methods which can be pipelined to produce the desired result. 
    answerList.stream().mapToInt(Integer::intValue).toArray();

Graph or Adjacency List

An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex and each element in its linked list represents the other vertices that form an edge with the vertex.

  • A graph can be best implemented using a List<List>. Inorder refers to how many nodes a particular node is dependent on. The source will have an edge to the dependent, dependent will be a vertex in the graph to which a list of sources is connected. Suppose a,b,d,e is dependent on c and a,d,e is also dependent on f. c will be dependent or the vertex which will have an edge from a,b,d,e. f will be dependent or vertex which will have an edge from a,d,e. No of dependents or inorder for a,d,e will be 2 ie c & f. No of dependents or inorder for b will be 1 ie c.

  • the source can also become a vertex and the dependent can be an edge

  • whichever comes first will be the vertex

  • inorder will always point to edges

  • Topologic sorting tells us in which sequence we need to pick up or finish tasks

//1->2
    //1 is dependent on 2
    //2 has an edge coming inward so indegree++
    //1 has an edge going outwards so indegree-- or outdegree++
    // 2 is vertex and 1 is edge
    //list appearance
    //2 <- 1, 3, 4
//997. Find the Town Judge
//t[0] is dependent on t[1]
    class Solution {
  public int findJudge(int n, int[][] trust) {

      int[] count = new int[n + 1];
      for (int[] t : trust) {
          // outdegree
          count[t[0]]--;
          // indegree
          count[t[1]]++;
      }
      for (int i = 1; i <= n; i++)
          if (count[i] == n - 1)
              return i;
      return -1;
  }
}
//Alien Dictionary
//topological sorting
private List<Integer> topoSort(int v, List<List<Integer>> adj) {
    int indegree[] = new int[v];
    for (int i = 0; i < v; i++)
        for (int it : adj.get(i))
            indegree[it]++;

    Queue<Integer> q = new LinkedList();
    for (int i = 0; i < v; i++)
        if (indegree[i] == 0)
            q.add(i);

    List<Integer> topo = new ArrayList();
    while (!q.isEmpty()) {
        int node = q.poll();
        topo.add(node);

        for (int it : adj.get(node)) {
            indegree[it]--;
            if (indegree[it] == 0)
                q.add(it);
        }
    }
    return topo;
}

//initialize
List<Integer>[] bucket = new ArrayList[nums.length+1];
if(bucket[freq]==null)
                bucket[freq] = new ArrayList();
bucket[freq].add(num);
  • the second method uses a hashmap

  • the advantage of using the map

  • dynamic length

  • can have any vertex value

  • no duplicate edges BCS of set

//vertex, edge
        Map<Integer, Set<Integer>> map = new HashMap();
        for(int i=0; i<numCourses; i++)
            map.put(i, new HashSet());
// Adjacency list syntax
class Solution {
    List<List<Integer>> al = new ArrayList();
    public long countPairs(int n, int[][] edges) {

        for(int i=0; i<n; i++)
            al.add(new ArrayList());
        //make graph
        for(int[] edge: edges) {
            al.get(edge[0]).add(edge[1]);
            al.get(edge[1]).add(edge[0]);
        }

        long res=0, sum=n;
        boolean[] visited = new boolean[n];
        for(int i=0; i<n; i++) {
            if(!visited[i]) {
                //find size of connected set
                int curr = dfs(i, visited, new int[1]);
                sum -= curr;
                res += curr * sum;
            }
        }
        return res;
    }

    private int dfs(int node, boolean[] visited, int[] count) {
        if(visited[node])
            return count[0];
        visited[node] = true;
        count[0]++;
        for(int curr: al.get(node))
            dfs(curr,visited,count);
        return count[0];
    }
}
// Adjacency list syntax 2
// 2385. Amount of Time for Binary Tree to Be Infected
private Map<Integer, List<Integer>> adjacencyList = new HashMap();
if (root.left != null) {
    adjacencyList.computeIfAbsent(root.val, k -> new ArrayList()).add(root.left.val);
    adjacencyList.computeIfAbsent(root.left.val, k -> new ArrayList()).add(root.val);
}
// Traversing adjacency list BFS
q.add(start);
while (!q.isEmpty()) {
    time++;
    int size = q.size();
    while (size-- > 0) {
        int curr = q.poll();
        v.add(curr);

        if (adjacencyList.containsKey(curr))
            for (int neigh : adjacencyList.get(curr))
                if (!v.contains(neigh))
                    q.add(neigh);
    }
}

Disjoint Set

  • A disjoint-set data structure is defined as one that keeps track of a set of elements partitioned into several disjoint (non-overlapping) subsets.

  • A union-find algorithm is an algorithm that performs two useful operations on such a data structure

    • Find: Determine which subset a particular element is in. This can determine if two elements are in the same subset.

    • Union: Join two subsets into a single subset. Here first we have to check if the two subsets belong to the same set. If not, then we cannot perform union.

  • Applications of Disjoint Set Union

    • Kruskal’s Minimum Spanning Tree Algorithm, Job Sequencing Problem, Cycle Detection, Number of pairs, City With the Smallest Number of Neighbors at a Threshold Distance
  • DFS, BFS, and disjoint sets are used to parse connected components.

  • It is just like an adjacency list. But each edge size will be equal to one and will directly point to the parent.

  • Like an adjacency list, it is used to connect undirected edges.

  • Suppose we have 0,1,2,3,4,5,6,7,8,9 people

  • we can add friend addFrnd(2,3) and addFrnd(4,5)

  • Now if we check areFrnd(2,3) and areFrnd(4,5) it will return true.

  • Now if we call addFrnd(2,5). 2,3,4,5 will form a set in which all will be friends.

  • Here addFrnd refers to union and areFrnd refers to find operation.

  • Similarly, we can have another set of friends like 6,7,8,9,0,1

  • 0->1
    1 -> 7
    2 -> 4
    3 -> 2

  • You can see all are connected to each other.

  • Disjoint set union will consist of a union of different sets like above. like-set 1 - 1,2,3,4,5 set 2- 6,7,8,9,0

  • We have a union operation, where we connect all edges

  • We use union by rank, to choose parent based on rank.

  • 1,2,3,4,5 & 6,7 . If we add 1 as a parent of 6, 1 rank will remain the same as 4 and access 4 at the same time.

  • But if we add 6 as a parent of 1, 6 ranks will change from 1 to 5 and we will need one extra step to access 4.

  • we have a find operation, to find parent

  • we use Path Compression to assign new parent to shorten the path

  • 1->2->3->4->5

  • Suppose we are searching for the parent of 1. It will traverse through 2,3,4 to reach 5 while returning it will assign 5 as a parent to all nodes to reduce the path.

  • BCS of the union by rank and path compression, time & space complexity of union, and find operation remains O(n), no matter how large the data set.

  • Time complexity

  • Union - O(1)

  • Find - O(5) max ie O(1)

  • Space complexity

  • O(n) for DSU to store the mapping of parent and child

  • Union-Find (Disjoint Set) - Hideous Humpback Freak

  • The Simple Tutorial to Disjoint Set (Union Find Algorithm) | Algorithms,  Blockchain and Cloud

  • Union Find Algorithm

  • Syntax example

  • below syntax will handle both zero and one indexed node. No need to pass n+1 for one indexed node.

  • In the case of zero-indexed last index will not be used and in the case of one-indexed 0 index will not be used.

  • So always pass DSU dsu_alice = new DSU(n); for both zero and one indexed nodes. ie actual no of nodes :).

// Disjoint Set Syntax
class Solution {

    public long countPairs(int n, int[][] edges) {
        DSU d = new DSU(n);
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int e[] : edges) {
            d.union(e[0], e[1]);
        }
        for (int i = 0; i < n; i++) {
            int p = d.findParent(i);
            map.put(p, map.getOrDefault(p, 0) + 1);
        }
        long ans = 0, sum = 0;
        for (int x : map.values()) sum += (long) x;
        for (int x : map.values()) {
            ans += (long) x * (long) (sum - (long) x);
            sum -= x;
    }
    return ans;
}

class DSU {
        int rank[];
        int parent[];
        int distinctComponents;

        DSU(int n) {
            rank = new int[n + 1];
            parent = new int[n + 1];
            distinctComponents = n;
            for (int i = 1; i <= n; i++) {
                parent[i] = i;
            }
        }

        int findParent(int node) {
            if (parent[node] == node) return node;
            return parent[node] = findParent(parent[node]);
        }

        boolean union(int x, int y) {
            int px = findParent(x);
            int py = findParent(y);
            if (px == py) return false;
            if (rank[px] < rank[py]) {
                parent[px] = py;
            } else if (rank[px] > rank[py]) {
                parent[py] = px;
            } else {
                parent[px] = py;
                rank[py]++;
            }
            distinctComponents--;
            return true;
        }

        boolean united() {
            return distinctComponents == 1;
        }

        boolean connected(int p, int q) {
            return findParent(p) == findParent(q);
        }

        void reset(int p) {
            parent[p] = p;
            rank[p] = 0;
        }

    }

to find the max or min value in java

//same will be for min
int a = Integer.MAX_VALUE;
long a = Long.MAX_VALUE;

Math methods

//same will be for min
//find max of two values
Math.max(nums[0], nums[1]);

//find ceiling(greater or equal to) of double or float no
Math.ceil(double value);
//1.33 -> 2.0 (ceiling value), 1.0 -> 1.0, 3 -> 3.0

//find floor(equal or less than no) of double or float no
Math.floor()
//1.33 -> 1 (floor value), 1.0 -> 1.0, 3 -> 3.0
  • absolute value
//it will return the absolute value of any number 
//means if -ve will be negated otherwise remains the same
Math.abs(g)
  • generate random values
// Math.random() returns a random number between 0.0-0.99.
double rnd = Math.random();

// rnd1 is an integer in the range 0-9 (including 9).
int rnd1 = (int)(Math.random()*10);

// rnd2 is in the range 1-10 (including 10). The parentheses are necessary!
int rnd2 = (int)(Math.random()*10) + 1;

// rnd3 is in the range 5-10 (including 10). The range is 10-5+1 = 6.
int rnd3 = (int)(Math.random()*6) + 5;

//you can specify the range you want to generate using *6 or *10. 
//you can specify the start of random no from +1 or +5. 
//It will generate 6 and 10 random values from min 1 or 5
// create random object
        Random ran = new Random();
int nxt = ran.nextInt(10);
System.out.println
        ("Random number between 0 and 10 is : " + nxt);
Random number between 0 and 9 is : 4

ternary operator in java

return (negative==true)? -result : result;

Switch in java

  • Here is a nested switch example
 String Branch = "CSE";
          int year = 2;

          switch (year) {
          case 1:
              System.out.println("elective courses : Advance english, Algebra");
              break;
          case 2:
              switch (Branch) // nested switch
              {
              case "CSE":
              case "CCE":
                  System.out.println("elective courses : Machine Learning, Big Data");
                  break;

              case "ECE":
                  System.out.println("elective courses : Antenna Engineering");
                  break;

              default:
                  System.out.println("Elective courses : Optimization");
              }
          }

Stream In Java

  • Introduced in Java 8, Stream API is a way to express and process collections of objects.

  • Enable us to perform operations like filtering, mapping, reducing and sorting.

  • A stream consists of a source followed by zero or more intermediate methods combined (pipelined) and a terminal method to process the objects obtained from the source as per the methods described.

  • Stream is used to compute elements as per the pipelined methods without altering the original value of the object.

      // 1930. Unique Length-3 Palindromic Subsequences
      // unique chars count
          if (first[i] < last[i])
              res += s.substring(first[i] + 1, last[i]).chars().distinct().count();
      //char method will return an stream of ints, 
      //distinct method will seperate distinct values from it
      //count terminal method will count those distinct values.
    
  • two types of operations in stream

    • Intermediate Operations

    • Terminate Operations

  • Intermediate Operations

    • Methods are chained together.

    • Intermediate operations transform a stream into another stream.

    • It enables the concept of filtering where one method filters data and passes it to another method after processing.

    • Important Intermediate Operations

    • map()

    • The map method is used to return a stream consisting of the results of applying the given function to the elements of this stream.

List number = Arrays.asList(2,3,4,5);
List square = number.stream().map(x->x*x).collect(Collectors.toList());
  • Terminate Operations

  • Terminal Operations are the type of Operations that return the result. These Operations are not processed further just return a final result value.

  • Important Terminal Operations

  • collect()

  • The collect method is used to return the result of the intermediate operations performed on the stream.

List number = Arrays.asList(2,3,4,5,3);
Set square = number.stream().map(x->x*x).collect(Collectors.toSet());

Tuple

  • Tuple

  • The word “tuple” means “a data structure consisting of multiple parts”.

  • Hence Tuples can be defined as a data structure that can hold multiple values and these values may/may not be related to each other.

  • eg - [Geeks, 123, &#*@]

  • JavaTuples allows maximum of 10 tuples classes. For 2 it is pair class.

//intialization
Pair<TreeNode, Integer> p = new Pair(root, col);

//get key
root = p.getKey();
//get value
col = p.getValue();
//set key
KeyValue<Integer, String> kv= KeyValue.with(Integer.valueOf(1),"1");
KeyValue<String, String> kv1 = kv.setKey("One");
System.out.println(kv1);
//[One, 1]

Pair Class

  • Suppose you have data like {{key,value1},value2}. Here the key is {key, value} pair. So we need to use another hashmap for it. and it will become a nested hashmap.

  • here Pair save us by treating it as a single variable and single data.

  • It is used if we want to keep a pair of values together.

//1187. Make Array Strictly Increasing
//its uses alongwith map
HashMap<Pair<Integer, Integer>, Integer> map = new HashMap();

map.put(new Pair<>(currIdx, prev), res);

map.containsKey(new Pair<>(currIdx, prev))

map.get(new Pair<>(currIdx, prev))

//provides following methods
Pair (K key, V value) -> creates a new pair

boolean equals() -> compares two pair objs

String toString() -> returns string equivalent

K getKey() -> returns key

V getValue() -> returns value

int hashCode() -> generate hashcode for pair obj

//pair obj
Pair<Integer, String> p
            = new Pair<Integer, String>(10, "Hello Geeks!");
  • We can create our own custom pair class, it is easy to use and access its elements

  • The limitation it will have is a fixed type

//custom class
//907. Sum of Subarray Minimums
class Pair {
    int value;
    int index;

    public Pair(int value, int index) {
        this.value = value;
        this.index = index;
    }
}

//some common template
while (!next.isEmpty() && next.peek().value > arr[i]) {
    Pair x = next.pop();
    right[x.index] = i - x.index;
}
next.push(new Pair(arr[i], i));

HashSet

  • Useful methods

Set

//to declare HashSet
HashSet<Character> hash_set = new HashSet();

//initialize set
HashSet<Character> vowels = new HashSet(Arrays.asList('a','e','i','o','u'));

//add nos
//it will return true if no is added successfully else false
set.add("One");

//remove no
set.remove("One");

//remove all no
set.clear();

//check no in set
contains(element) //O(1)

//convert set to array
toArray()

//to find size
hash_set.size();

//to convert list to set
Set<String> wordSet = new HashSet(wordList);

Linked List

  • You can use a custom linked list class to implement a linked list or you can use a predefined LinkedList class to create a linked list. In the case of a custom class, you need to define your own add and remove nodes methods.

  • LinkedList in Java

  • This class is an implementation of the LinkedList data structure which is a linear data structure where the elements are not stored in contiguous locations and every element is a separate object with a data part and address part.

  • when you create a new node it will have a new address and that address will have data or ptrs to another node address.

  • we do not delete this object. So to make it look like delete we will update the next ptrs of its connecting node.

Useful methods

//to create new list using custom linked list class
ListNode tempNode = new ListNode();

//to create new list using pre-defined linked list class
LinkedList ll = new LinkedList();  

// to have multiple nodes with the same reference. 
ListNode currNode = tempNode;

// to create a node with a null value
ListNode prev = null;

//This method Appends the specified element to the end of this list.
add(E e)
ll.add("A");

//This method Inserts the specified element at the specified position in this list.
//add(int index, E element)

//This method retrieves but does not remove, the head (first element) of this list.
//peek()

//This method retrieves and removes the head (first element) of this list.
//poll()

Internal working of the linked list

//24. Swap Nodes in Pairs
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {

        if(head==null || head.next==null)
            return head;

        ListNode dummyNode = new ListNode();
        ListNode prevNode = dummyNode;
        ListNode currNode = head;

        while(currNode!=null && currNode.next!=null) {
            prevNode.next = currNode.next;
            currNode.next = prevNode.next.next;
            prevNode.next.next = currNode;

            prevNode = currNode;
            currNode = currNode.next;
        }
        return dummyNode.next;
    }
}
  • dummyNode will point to random 1000 and head will point to random 2789 in memory

  • prevNode will point to the same 1000 as it was created from dummyNode.

  • currNode will point to the same 2789 as it is created from the head.

  • In the initial operation prevNode.next value changes while it is pointing to 1000 in memory.

  • So dummyNode value also changes BCS it is pointing to the same memory.

  • So we return dummyNode.next pointing to the head at the end. Even though there was no connection between dummyNode and head initially.

  • later prevNode memory will change to the next node memory 6000. when it moves forward. but dummyNode is still pointing to 1000.

  • Each new node in the linked list will have unique random memory and if some node is created with an existing node, it will point to the same memory.


Double Linked List

  • It is just like a linked list. It will have an extra pointer to point to the prev node. Java doesn't have a pre-defined class for this. The user has to create its own custom class to implement this. Users also need to define their own methods to add and remove nodes.

Doubly Linked ListDoubly Linked List In Java

HashMap or Map

to insert value in the map

//here it will fetch the value of the key and then add 1. If the key doesn't exist, It will //add the key to the map then it will assign 0 as its value, and then increase its value.
//the get symbolizes value to fetch, so keep value first
//the default symbolize default value to keep, so keep the default value second 

for(int n: nums){
            map.put(n, map.getOrDefault(n,0)+1);
        }
  • put value in the map if the key is absent or mapped to a null value.
//here it will check if char is absent then add char along with a new linked list

//It prevents key null check
HashMap<Character, Queue<String>> map = new HashMap();
map.putIfAbsent(s.charAt(i),new LinkedList());

//it will add a key alongwith with its value if it is not present in the map
//it will return the original value if key is present, if absent new value
//is computed and returned. you can use that value as reference to update it.

//It prevents key null check and updating values sepearately
//It returns values
orderedGroups.computeIfAbsent(group[item], k -> new ArrayList()).add(item);

//1282. Group the People Given the Group Size They Belong To
List<Integer> list = groups.computeIfAbsent(groupSizes[i],
                    k -> new ArrayList());
list.add(i)

Useful method of map

HashMap

//declare map
Map<String, Integer> map = new HashMap();

//declare map of fixed length
HashMap<Integer, Integer>[] map = new HashMap[length];

//you can even assign values to it serially
for(int i=0; i<length; i++)
            map[i] = new HashMap();

//here integer will be key & stack will be its value
//we need to put inbuilt dsa methods in map as we use it
//like Stack<Integer> not just Stack and it will be empty by default so we need to //assign some value to it. 
HashMap<Integer, Stack<Integer>> freqStack = new HashMap();

//add item
map.put(s, index);

//check key
map.containsKey(s)

//check value
containsValue(Object value)

//Returns a Set view of the keys contained in this map.
keySet()

//Returns a Collection view of the values contained in this map.
values()

//fetch value
//returns null if no value found
get(Object key)
int count = counts.get(key);

//remove no
remove(Object key)

//check empty
isEmpty()

//check size
size()

//It will store keys and values as a single object
map.entrySet()

//access key and value of entry object
entry.getKey()
entry.getValue()

//traverse entrySet of map
for(Map.Entry<Integer,Integer> entry: map.entrySet()){
            maxHeap.add(entry);
        }

//parse keySet of map
String result = "";
        for(String key: counts.keySet()) {
            if(result.equals("") || counts.get(key) > counts.get(result)) 
                result = key;
        }

//return a list of map values
    return new ArrayList(map.values());
  • clear func will delete all the keys and values from the map
Hash_Map.clear()
  • if the map value is an object, you can directly update its value without putting it again using the key.

  • if the map value is a primitive data type it will throw an error "found value instead of a variable".


TreeMap

  • It is the same as HashMap instead maintains ascending order(Sorted using the natural order of its key). In short, it will contain keys sorted in ascending order.

Useful methods TreeMap

//declaration
TreeMap<String, Integer> map = new TreeMap();

//add no
//it will take O(log n) time to insert bcs it needs to sort keys
map.put(products[index], index);

//The ceilingKey() function of TreeMap Class returns the least key greater than or equal to the given key or null if such a key is absent.
String celling = map.ceilingKey(key);

//The floorKey() method is used to return the greatest key less than or equal to the given key from the parameter or null if such a key is absent.
String floor = map.floorKey(key+ "{");

//returns the first key
return valueTm.firstKey();

//returns the last key
return valueTm.lastKey();

//will insert mappings only if absent
valueTm.putIfAbsent(price,new HashSet());

//will delete mapping for the key
valueTm.remove(oldPrice);

TreeMap of fixed size

//1146. Snapshot Array
TreeMap<Integer, Integer>[] A=new TreeMap[length];
    It will create an empty tree map at each index with index just as ref. There will be no value in it.
    0 -> TreeMap()
    1 -> TreeMap()
    Here 0 & 1 doesnt exist & used just as ref for index.
    for(int i=0; i<length; i++) {
                A[i] = new TreeMap();
                A[i].put(0,0);
            }

PriorityQueue

  • It is just like a queue except here you can remove elements based on priority. MinHeap and MaxHeap are implemented using this in java. It takes O(log n) time to search for any element in PriorityQueue. a-b indicates ascending order means min-heap. b-a indicates descending order means max heap. These refer to the same single value. These are not two different values. There is a comparison between like within start or end times. It takes O(log n) to both add and remove elements from PriorityQueue.

  • we can even sort custom classes objs using pq, just provide its type to pq

HashMap<String, PriorityQueue<Food>> cMap = new HashMap<>();
// update cuisine map with cuisine key and empty pq
cMap.putIfAbsent(cuisines[i], new PriorityQueue<>(
        (a, b) -> b.rating == a.rating ? a.name.compareTo(b.name) : b.rating - a.rating));

MinHeap

  • In this minimum element will be at the top. It will be like a tree. It is really helpful in finding the kth smallest and largest elements. For largest just keep the heap size as k.

Declaration

PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
PriorityQueue<Integer> allocator = new PriorityQueue<>((a,b)->a-b);

//array sorting  
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a,b)->a[0]!=b[0]?a[0]-b[0]:a[1]-b[1]);

//adding array
minHeap.add(new int[]{soldiers,i});

//fetching only second value
res[i] = minHeap.poll()[1];

//add map entry to heap
//here if freq is equal sort reverse lexicographically, if not sort frequency in ascending order. here word and freq both are getting added as an object
//The compareTo() method compares two strings lexicographically
//and is mostly used in pq for sorting, return 0 if strings are equal
//< 0, if the string is less than other string
//> 0 if the string is greater than other string
PriorityQueue<Map.Entry<String, Integer>> pq = new PriorityQueue<>(
        (a,b) -> a.getValue()==b.getValue() ? b.getKey().compareTo(a.getKey()) : a.getValue() - b.getValue()
        );

//suppose you only need the key in sorted form based on its value
//we can only add a key and sort it by fetching value from the map.
//no need to add values if you do not need them. It will save a lot of space.
//here it is adding all the keys based on their values.
PriorityQueue<Character> maxHeap = new PriorityQueue((a,b)->map.get(b)-map.get(a));
        maxHeap.addAll(map.keySet());

MaxHeap

  • In this maximum element will be at the top. It will be like a tree. You have to add a comparator in PriorityQueue to implement MaxHeap because by default it will behave like MinHeap.

Declaration

PriorityQueue<Map.Entry<Integer, Integer>> maxHeap = 
                         new PriorityQueue<>((a,b)->(b.getValue()-a.getValue()));

useful methods of the heap

//It will add element
maxHeap.add(entry);

//It will remove top element and return
maxHeap.poll();

//It will just return top element
maxHeap.peek();

//it will return size
maxHeap.size()

//check if it is empty
maxHeap.isEmpty();

//check if heap contains a no
pq.contains(num)

Convert minHeap to maxHeap and vice-versa

you can convert minHeap to maxHeap and vice-versa by popping the nos if it exceeds the k size of the heap. In the case of minHeap, you will get maxHeap with k largest nos. In the case of maxHeap, you will get minHeap with k smallest nos.

  • if you keep minHeap size to be k and poll() other elements. Then you will get kth largest no at the top. BCS last no of min heap will be the largest.

  • if you keep maxHeap size to be k and poll() other elements. Then you will get kth smallest no at the top. BCS last no of the max heap will be the smallest.

  • it is useful for kth smallest and largest no problem. It reduces complexity and space.

//converting minHeap to maxHeap
minHeap.add(val);
                if(minHeap.size()>k)
                    minHeap.poll();

More details

Comparatorheap implementation


  • The time complexity is O(log n). In this we search elements on one side, ignoring the other side repeatedly until we get an answer at mid position. Obviously, binary search can be applied to the sorted array BCS you need to ignore one side.
//unique elements
function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

//unique element alternate
private int findNext(int curr, int[][] jobs) {
        int lo = curr + 1;
        int hi = jobs.length - 1;
        while (lo <= hi) {
            int mid = lo + (hi - lo) / 2;
            if (jobs[mid][0] >= jobs[curr][1]) {
                if (jobs[mid - 1][0] >= jobs[curr][1])
                    hi = mid - 1;
                else
                    return mid;
            } else
                lo = mid + 1;
        }
        return -1;
    }

//reverse binary search for unique elements
//in this elements are sorted in decreasing order
//1095. Find in Mountain Array
 // find target in the right of peak
        l = peak;
        r = n - 1;
        while (l <= r) {
            mid = l + (r - l) / 2;
            if (mountainArr.get(mid) > target)
                l = mid + 1;
            else if (mountainArr.get(mid) < target)
                r = mid - 1;
            else
                return mid;
        }
        return -1;
  • duplicate elements

      //leftmost element
      function binary_search_leftmost(A, n, T):
          L := 0
          R := n
          while L < R:
              m := floor((L + R) / 2)
              if A[m] < T:
                  L := m + 1
              else:
                  R := m
          return L
      //practical example
       private int findLeft(int[] nums, int target) {
              int left = 0, right = nums.length;
              Boolean exist = false;
              while (left < right) {
                  int mid = left + (right - left) / 2;
                  if (nums[mid] < target)
                      left = mid + 1;
                  else {
                      right = mid;
                      if (nums[mid] == target)
                          exist = true;
                  }
    
              }
              return exist ? left : -1;
          }
    
      //rightmost element
      function binary_search_rightmost(A, n, T):
          L := 0
          R := n
          while L < R:
              m := floor((L + R) / 2)
              if A[m] > T:
                  R := m
              else:
                  L := m + 1
          return R - 1
      //practical example
       private int findRight(int[] nums, int target) {
              int left = 0, right = nums.length;
              Boolean exist = false;
              while (left < right) {
                  int mid = left + (right - left) / 2;
                  if (nums[mid] > target) {
                      right = mid;
                  } else {
                      left = mid + 1;
                      if (nums[mid] == target)
                          exist = true;
                  }
    
              }
              return exist ? right - 1 : -1;
          }
    
  • If you have unique elements then all three algorithms will work

      //2251. Number of Flowers in Full Bloom
      //here left will return the exact count of elements
      //less than or equal to the target
      if (arr[mid] <= target) {
          left = mid + 1;
      [1,3,4,9], t=7, l=3
      //l is pointing to index where 
      //all elements are either less or equal to 7
    
      //here left will return exact count of elements less than target
      if (arr[mid] < target) {
          left = mid + 1;
      [6,7,12,13], t=7, l=1
      //l is pointing to index where all elements are strictly less than 7
    
  • references


Stack

  • It is like a real-life stack. No which enters the last leaves first(LIFO). No which enters first leaves last(FILO).
//Intialization
Stack<TreeNode> stack = new Stack();

//check if it is empty
stack.isEmpty();

//add no in stack
stack.push(root);

//to return and remove a value from the top
stack.pop();

// to return top value without removing it
stack.peek();

Monotonic Stack

  • It is a stack that is strictly increasing or decreasing

  • In this mainly index of nos is added instead of the no

  • It is used for the following purposes

    • range of queries in an array situation

    • minima/maxima elementts

    • no, popped from the stack will never be utilized again

  • The biggest advantage is that we can get the nearest smallest or greatest element depending on stack type, by just retrieving the stack top element in O(1) time

  • ref - Introduction to Monotonic Stack


Queue

  • Queue is like a real-life queue. It follows FIFO(first in first out). In this nos which enters first, exit first. In java, Queue is an interface that will be implemented by diff classes like - PriorityQueue, LinkedList, and PriorityBlockingQueue.

ref - Queue

// Creating an empty priority queue
Queue<Integer> pQueue = new PriorityQueue<Integer>();

// Creating empty Queue of integer
Queue<Integer> queue = new LinkedList();

//queue of int array
Queue<int[]> queue = new LinkedList();

//add int array to queue
queue.add(new int[]{row, col});

//methods will remain the same for both
//Add nos
ll.add(10);

//print top no
ll.peek();

//print and remove top no
ll.poll();

//check if it is empty
queue.isEmpty()

//check size
queue.size()

//both stack and queue can hold null
queue.add(null);

Deque

  • It is like a queue except in this nos can be added and removed both from front and back. It is an interface implemented by ArrayDeque or LinkedList class.

Notes

  • Deque has a similar declaration to queue.

  • Add and remove behaviour and method are the same as a queue. It will add at last and remove from first by default.

Useful methods Deque

 // Initializing an deque
        Deque<Pair<Integer,Integer>> hits = new LinkedList();
   Deque<Integer> de_que  = new ArrayDeque<Integer>(10);

//add nos at first or last
//offer is preferred over add bcs it doesn't throw exception when dequeue is full
        offerFirst(element) 
        offerLast(element)

//It will add no at last
add() 
//It will add no at first
addFirst()
//It will add no at last
addLast()

//remove no from first or last
       System.out.println(dq.pollFirst());
        System.out.println(dq.pollLast());
//remove from first 
poll()

//Iterating through dequeue
    for (Iterator itr = dq.iterator();
             itr.hasNext();) {
            System.out.print(itr.next() + " ");
        }

//peek methods
  peekFirst()
  peekLast()

Traverse Tree

  • DFS

  • BFS

DFS

  • DFS stands for depth-first search. In this tree will be traversed on the left side first then the right side. Like it will be traversed in left depth first then in the right depth.

Stack is generally used for DFS. Three methods for dfs are -

  • inorder traversal - left->root->right. In this complete left side is traversed than the root then the right side of bst is traversed.

  • inorder traversal gives us ascending order of bst. BCS bst will have parent greater than left and lesser than right.

  • pre-order traversal - root->left->right. In this root is traversed first then the complete left side nodes are traversed then complete right side nodes are traversed. pre will refer to root.

  • post-order traversal - left->right->root. In this complete left nodes are traversed. then right nodes are traversed. then the root is traversed. post will refer to root.

BFS

  • BFS stands for breadth-first search. It is also called level order traversal.

In this, you will traverse nodes level-wise. like root level will be traversed first then second-level nodes will be traversed. The queue is generally used for BFS.


Binary Search Tree

  • Binary Search Tree is a node-based binary tree data structure that has the following properties:

    • The left subtree of a node contains only nodes with keys lesser than the node’s key or null.

    • The right subtree of a node contains only nodes with keys greater than the node’s key or null.

    • The left and right subtree each must also be a binary search tree.

  • When we do inorder traversal of bst it returns a sorted list. Note post-order and pre-order traversal doesn't return a sorted list.


Inorder Tree Traversal (DFS)

  • Traverse the left subtree, i.e., call Inorder(left->subtree)

  • Visit the root.

  • Traverse the right subtree, i.e., call Inorder(right->subtree)

      //template
      //94. Binary Tree Inorder Traversal
      public List<Integer> inorderTraversal(TreeNode root) {
          List<Integer> list = new ArrayList<>();
          if(root == null) return list;
          Stack<TreeNode> stack = new Stack<>();
          while(root != null || !stack.empty()){
              while(root != null){
                  stack.push(root);
                  root = root.left;
              }
              root = stack.pop();
              list.add(root.val);
              root = root.right;
    
          }
          return list;
      }
    

Post-Order Tree Traversal (DFS)

  • left->right->root
//2265. Count Nodes Equal to Average of Subtree
//recursive
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
class Solution {
    int res = 0;

    public int averageOfSubtree(TreeNode root) {
        dfs(root);
        return res;
    }

    private int[] dfs(TreeNode node) {
        if (node == null)
            return new int[] { 0, 0 };

        int[] left = dfs(node.left);
        int[] right = dfs(node.right);

        int currSum = left[0] + right[0] + node.val;
        int currCount = left[1] + right[1] + 1;

        if (currSum / currCount == node.val)
            res++;
        return new int[] { currSum, currCount };
    }
}

BFS or Level Order Traversal

  • For each node, first, the node is visited and then its child nodes are put in a FIFO queue. Then again the first node is popped out and then its child nodes are put in a FIFO queue and repeat until the queue becomes empty.

      //1161. Maximum Level Sum of a Binary Tree
    
      /**
       * Definition for a binary tree node.
       * public class TreeNode {
       *     int val;
       *     TreeNode left;
       *     TreeNode right;
       *     TreeNode() {}
       *     TreeNode(int val) { this.val = val; }
       *     TreeNode(int val, TreeNode left, TreeNode right) {
       *         this.val = val;
       *         this.left = left;
       *         this.right = right;
       *     }
       * }
       */
      class Solution {
          public int maxLevelSum(TreeNode root) {
              int max=Integer.MIN_VALUE, maxLevel=1, level=0;
              Queue<TreeNode> q = new LinkedList();
              q.add(root);
    
              while(!q.isEmpty()) {
                  level++;
                  int size=q.size(), sum=0;
                  while(size-->0) {
                      TreeNode n = q.poll();
                      sum += n.val;
                      if(n.left!=null)
                          q.add(n.left);
                      if(n.right!=null)
                          q.add(n.right);
                  }
                  if(max<sum) {
                      max=sum;
                      maxLevel= level;
                  }
              }
              return maxLevel;
          }
      }
    
    • Note - Both DFS and BFS start from a base case whose answer is certain. In the case of DFS in recursion, res is returned by base case and using which rest of the computation happens

Continue

  • It will ignore all the statements after it and ask the inclosing loop to continue with the next iteration.
//It will ignore the x,y,z execution and continue with next iteration.
while() {
continue;
x
y
z
}

Do Nothing

  • Use ";" to do nothing. It is similar to pass in python. It is different than continue. continue skips execution of the rest of the statement in the enclosing loop. It will continue the execution of the rest of the statements.
 if(i==0)
      ;
else if(j==0)
       ;

Break

  • It will break the enclosing loop and take the execution after the enclosing loop.
//it will break the loop and take execution to x.
while() {
break;
}
x;

Pass by value & reference

  • In java pass-by-value is followed. If you make changes to the object it will show in the main memory. A copy of the original reference is passed. If you change the reference of the object then the change will not show in the main memory.

We cannot pass variables through reference, you have to create a global variable or use an object of a particular type like an array to pass it as a value.

//here we are using array as variable
int[] diameter = new int[1];
height(root, diameter);
private int height(TreeNode node, int[] dia)

Math Formulas

//Sum of n natural numbers
n(n+1)/2

Shift Operator

What does a bitwise shift (left or right) do and what is it used for?

Signed Left Shift Operator in Java

  • The left shift operator moves all bits by a given number of bits to the left.

  • In the example above, the binary number 0010 (in decimal 2) becomes 1000 after shifting the bits to the left (in decimal 8).

  • It is represented by << .

  • x = x * 2^value (normal operation)

  • x << value (bit-wise operation)

  • x = x * 16 (which is the same as 2^4)

  • The left shift equivalent would be x = x << 4

 System.out.println(2<<1); --> 4
System.out.println(2<<2);  --> 8
System.out.println(2<<3);  --> 16

Signed Right Shift Operator in Java

  • The right shift operator moves all bits by a given number of bits to the right.

  • In the example above, the binary number 1000 (in decimal 8) becomes 0010 after shifting the bits to the right (in decimal 2).

  • It is represented by >> .

  • x = x / 2^value (normal arithmetic operation)

  • x >> value (bit-wise operation)

  • x = x / 8 (which is the same as 2^3)

  • The right shift equivalent would be x = x >> 3

System.out.println(4>>1);  --> 2
System.out.println(16>>2); --> 4
System.out.println(40>>3);  --> 5

Note

  • the shifting of the binary digit is multiplying and dividing the value. so multiplication and division are simple terms of value when you shift binary operators.

Un-Signed Shift Operator in Java

  • >>> represents an un-signed right shift operator, it is used for bit shifting in un-signed integers.

  • It works the same as signed operators just that they are used on unsigned nos.

  • Java uses signed int, which means out of 32 bits, 16 bits represent positive nos and the rest 16 bits represent negative nos.

  • Once max limit Integer.MAX_VALUE is reached it will again start from -1. ie Integer.MAX_VALUE+1 is equal to -1.

  • A signed integer is a 32-bit datum that encodes an integer in the range [-2147483648 to 2147483647]. An unsigned integer is a 32-bit datum that encodes a nonnegative integer in the range [0 to 4294967295].


Round a Number to n Decimal Places

double number = 145.34567;
DecimalFormat df_obj = new DecimalFormat("#.###");
System.out.println(df_obj.format(number));
145.346

Void Return Type

  • we can use return; for functions that have return types as a void to return something based on certain conditions.

Real-time application of Data Structures

Real-time application of Data Structures

Important Topics

Bitmasking

  • Bitmasking in Java

  • Bitmasking allows us to store multiple values inside one numerical variable. Instead of thinking about this variable as a whole number, we treat its every bit as a separate value.

  • Because a bit can equal either zero or one, we can also think of it as either false or true. We can also slice a group of bits and treat them as a smaller number variable or even a String.

  • you can better understand its use with strings

  • suppose there is a string, no matter how you shuffle its chars, it will have constant bitmask value.

  • ad and da will have the same bitmask value ie - 00000001001

  • you can also subtract the bitmask value of particular char from the bitmask value to obtain the bitmask value for the rest of the word.

  • ad - d = a, will be 00000001001 - 00000001000 will return you 00000000001 ie bitmask value of the remaining word a.

//bitmask function
 private int bitmask(String word) {
        int res = 0;
        for(char c: word.toCharArray()) {
            res += 1 << c-'a';
        }
        return res;
    }
  • to add something to the bitmap we use or operation and to find something in the bitmap we use and operation.
for(int j=0; j<n; j++) {
    for(int k=j+1; k<n; k++) {
        int new_mask= (1<<j) + (1<<k);
        if((mask&new_mask)==0) 
    }
}
  • Here we are marking we have seen the j and k combination in new_mask

  • Then we are checking if the new_mask is part of the existing mask, if it is it will return 1.

  • mask -> 011001100 new_mask-> 000001100 , ans=1

//864. Shortest Path to Get All Keys
//some examples of bitmasking

//addition and subtraction
(curr.keys == (1 << max) - 1), max = 4
10000 - 1 = 1111

//or operation to add something
keys |= 1 << (c - 'a'), char = c
0100

//and operation to find something
(1 << (c - 'A')) & keys, lock = C
0100 & 0100 = 1
  • Note - | operation is used to add something in bit masking and & operation is used to find something in bit masking.

  • we use | and & to perform or and operations instead of || and && symbols.

  • we can use normal integer to store bits

  • we can use bitCount method to count no of bits in the integer

//1239. Maximum Length of a Concatenated String with Unique Characters
int all = 0, dup = 0;
res = Math.max(res, Integer.bitCount(dp.get(i) | all));

Tabulation vs Memoization

Memoization

  • Top-down approach

  • Caches the results of function calls

  • Recursive implementation

  • Well-suited for problems with a relatively small set of inputs

  • Used when the subproblems have overlapping subproblems

Tabulation

  • Bottom-up approach

  • Stores the results of subproblems in a table

  • Iterative implementation

  • Well-suited for problems with a large set of inputs

  • Used when the subproblems do not overlap

References


Memoization

memoization

  • Memoization consists in caching the results of functions in order to speed them up when they are called several times with the same argument.

  • The first call implies computing and storing the result in memory before returning it.

  • Subsequent calls with the same parameter imply only fetching the previously stored value and returning it.

  • Suppose you need to do recursion on the array. so you can use a boolean array of same size to store visited cells as true, to avoid revisiting the cells again.

Recursion in java

Tree Traversals

  • you can better understand recursion through an inorder traversal in java.
 /* Given a binary tree, print its nodes in inorder*/
    void printInorder(Node node)
    {
        if (node == null)
            return;

        /* first recur on left child */
        printInorder(node.left);

        /* then print the data of node */
        System.out.print(node.key + " ");

        /* now recur on right child */
        printInorder(node.right);
    }
  • so here we are passing the same tree. So if any recursive call makes any changes to the tree it will be visible to all the recursive calls.

  • so suppose 1 ->2 ->3 is the tree. So its inorder traversal will be 2 -> 1 -> 3.

  • "printInorder(node.left);" so what will happen here is all left nodes of 1 will be traversed and printed. then it will print 1. and then all right nodes of 1 will be traversed and printed.

  • just note that the same object is going to be passed for all the recursive calls.

  • the trick here is first to go through one recursive call. Then visualize other recursive calls on the result of the previous one.

Topological sorting

  • Topological sorting

  • Topological Sorting

  • Topological sorting returns an order of tasks in which we can execute it, the task which has 0 dependencies comes first.

  • In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

image.png

  • Here A is dependent on B, D. A indegree will be 2.

  • B, D will be the vertex and A will be the edge to them.

  • time - O(V+E) space - O(V+E) where v and e are vertex and edge.

  • It is used to solve problems where there are constraints or there is a dependency between elements.

  • Basic Syntax of topological sort.

  • 2050. Parallel Courses III

  • Just like the diagram, Create a graph with vertex as nodes whose indegree or dependency is 0 and edge as nodes whose indegree or dependency is greater than 0.

  • like - 1->3, 2->3, 1,2 are vertex & 3 is edge with indegree as 2 and we can execute 3 after we have executed 1,2

  • We will keep an in-degree array to store dependency for each node.

  • traverse indegree and add nodes to the queue whose indegree or dependency is 0.

  • Then traverse its children and add them to the queue if their in-degree or dependency becomes 0.

//207. Course Schedule
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {

        int n = numCourses;
        int[] indegree = new int[n];
        List<List<Integer>> graph = new ArrayList();
        for (int i = 0; i < n; i++)
            graph.add(new ArrayList());

        for (int[] edge : prerequisites) {
            graph.get(edge[1]).add(edge[0]);
            indegree[edge[0]]++;
        }

        int count = 0;
        Queue<Integer> q = new LinkedList();
        for (int i = 0; i < n; i++)
            if (indegree[i] == 0)
                q.add(i);

        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int current = q.poll();
                count++;
                for (int neigh : graph.get(current)) {
                    if (--indegree[neigh] == 0)
                        q.add(neigh);
                }
            }
        }
        return count == n;
    }
}
//returns empty list in case of cycle
//1203. Sort Items by Groups Respecting Dependencies
private List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int[] indegree) {
        List<Integer> visited = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (Integer key : graph.keySet()) {
            if (indegree[key] == 0) {
                stack.add(key);
            }
        }

        while (!stack.isEmpty()) {
            Integer curr = stack.pop();
            visited.add(curr);

            for (Integer prev : graph.get(curr)) {
                indegree[prev]--;
                if (indegree[prev] == 0) {
                    stack.add(prev);
                }
            }
        }

        return visited.size() == graph.size() ? visited : new ArrayList<>();
    }

Dynamic Programming

  • Dynamic Programming

  • Dynamic Programming is recursion + memorization, in which we save state to avoid repeated computation.

  • We can use a new array to save states or save states in place in the same array.

  • Dynamic Programming is mainly an optimization over plain recursion.

  • Wherever we see a recursive solution that has repeated calls for the same inputs, we can optimize it using Dynamic Programming.

  • The idea is to simply store the results of subproblems so that we do not have to re-compute them when needed later. This simple optimization reduces time complexities from exponential to polynomial.

  • For example, if we write a simple recursive solution for Fibonacci Numbers, we get exponential time complexity and if we optimize it by storing solutions of subproblems, time complexity reduces to linear.

image.png

  • As given in the above ex in order to convert recursion to dp, just save or compute the state on which, you were going to call recursion and voila you got dp.

  • through dp, you avoid repeated computation or recursion of the same state

  • like rec(i,j+1) or dp[i][j+1], rec(i+1,j) or dp[i+1][j]

  • Here no need to call recursion as that state is already computed.

  • ref - 97. Interleaving String

//optimizations using n variables
//198. House Robber
//70. Climbing Stairs

Window Sliding Technique

  • Window Sliding Technique

  • Window Sliding Technique is a computational technique that aims to reduce the use of nested loops and replace them with a single loop, thereby reducing the time complexity.

  • number of sub-arrays for the current window are equal to the window size. ie right - left + 1 which gets added to the res

//ex- 930. Binary Subarrays With Sum
//first loop increase window from right using for or while loop
while loop() {
    //second loop keep shrinking window from left till suitable cond achieved
    //using while loop or some cond
    while loop() {
    }
    //do necessary computation to update res
    computation
}
return res
  • How to use Sliding Window Technique?

  • Find the size of the window required

  • Compute the result for 1st window, i.e. from the start of the data structure

  • Then use a loop to slide the window by 1, and keep computing the result window by window.

  • In this technique, we have two ptrs.

  • end ptr expands the window and start ptr decreases the window.

  • At a time only one ptr moves and the other remains fixed.

  • In this, the end ptr will be used to expand the window or traverse the array. Inside the for loop of end ptr, start ptr will keep shrinking the window till a condition is not satisfied. So tc is O(n).

  • eg - 424. Longest Repeating Character Replacement

//1456. Maximum Number of Vowels in a Substring of Given Length
//Input: s = "abciiidef", k = 3
//Output: 3
class Solution {
    public int maxVowels(String s, int k) {

        HashSet<Character> vowels = new HashSet(Arrays.asList('a','e','i','o','u'));
        int max_count=0;
        int count=0;
        for(int i=0;i<s.length();i++) {
            if(vowels.contains(s.charAt(i)))
                count++;
            //outside window
            if(i>=k && vowels.contains(s.charAt(i-k)))
                count--;
            max_count = Math.max(max_count,count);
        }
        return max_count;
    }
//another good example
//2090. K Radius Subarray Averages
  • From the above ex, you can see we first computed a 0-2 window.

  • Then we computed 0 & window 1-3

  • Then we see 0, 1 index are out of window and 0 index is already computed. So we computed 1 and window 2-4.

  • TC - O(n) SC - O(1)

  • sliding window template 1

//1838. Frequency of the Most Frequent Element
class Solution {
    public int maxFrequency(int[] nums, int k) {

        int res = 0;
        long sum = 0;
        Arrays.sort(nums);
        //increase window size using j ptr
        for (int i = 0, j = 0; j < nums.length; j++) {
            sum += nums[j];
            //base cond to shrink window, using i ptr
            //or to create a valid window
            while (sum + k < (long) nums[j] * (j - i + 1))
                sum -= nums[i++];
            //compute result
            res = Math.max(res, j - i + 1);
        }
        //return result
        return res;
    }
}
  • sliding window template (substrings)
//76. Minimum Window Substring
public static int findSubstring(String s) {
    int[] map = new int[128];
    int counter; // check whether the substring is valid
    int begin = 0, end = 0; // two pointers, one points to tail and one to head
    int d = 0; // the length of substring

    // initialize the hash map here
    Arrays.fill(map, 0);

    while (end < s.length()) {

        if (map[s.charAt(end++)]-- > 0) { /* modify counter here */ }

        while (/* counter condition */) {

            /* update d here if finding minimum */

            // increase begin to make it invalid/valid again

            if (map[s.charAt(begin++)]++ > 0) { /* modify counter here */ }
        }

        /* update d here if finding maximum */
    }
    return d;
}

Prefix Sum

  • It refers to the sum of all the elements we have traversed.

  • In the prefix array, prefix[i] will be equal to the sum of all elements before the ith index.

//2090. K Radius Subarray Averages
//prefix array
long[] prefixSum = new long[n + 1];
for (int i = 0; i < n; i++)
    prefixSum[i + 1] = prefixSum[i] + nums[i];

Trie

  • It is an easy and tricky but very imp topic. It is a data structure that the user creates on its own. It is used in autocomplete, spellchecker, etc. Like it will have 26 references to characters and each character will have its own 26 references. Like if you want to insert cat and car. Then it will first insert cat continuously than when you insert car. It will not insert ca again but from a there will be another branch that contains r character.

image.png

  • In computer science, a trie, also called digital tree or prefix tree, is a type of k-ary search tree, a tree data structure used for locating specific keys from within a set. These keys are most often strings, with links between nodes defined not by the entire key, but by individual characters.

  • Trie

Time complexity

//insert
time - O(n) space - O(n)

//search
time - O(n) space - O(1)
  • Implementation
//trie class
class TrieNode {
    Map<Character, TrieNode> children = new HashMap();
    boolean word = false;
}
//Trie Template
//208. Implement Trie (Prefix Tree)
class Trie {
    Node root;

    public Trie() {
        root = new Node();
    }

    public void insert(String word) {
        root.insert(word, 0);
    }

    public boolean search(String word) {
        return root.search(word, 0);
    }

    public boolean startsWith(String prefix) {
        return root.startsWith(prefix, 0);
    }

    class Node {
    Node[] nodes;
    boolean isEnd;
    String word;

    Node() {
        nodes = new Node[26];
    }

    private void insert(String word, int idx) {
        int n = word.length();
        // to avoid null ptr exception for string
        // no more chars to insert
        if (idx >= n)
            return;
        int i = word.charAt(idx) - 'a';
        if (nodes[i] == null)
            nodes[i] = new Node();
        if (idx == n - 1) {
            nodes[i].isEnd = true;
            nodes[i].word = word;
        }
        nodes[i].insert(word, idx + 1);
    }

    private boolean search(String word, int idx) {
        int n = word.length();
        // all chars searched
        if (idx >= n)
            return false;
        Node node = nodes[word.charAt(idx) - 'a'];
        if (node == null)
            return false;
        if (idx == n - 1 && node.isEnd)
            return true;
        return node.search(word, idx + 1);
    }

    private boolean startsWith(String prefix, int idx) {
        int n = prefix.length();
        // all chars searched
        if (idx >= n)
            return false;
        Node node = nodes[prefix.charAt(idx) - 'a'];
        if (node == null)
            return false;
        if (idx == n - 1)
            return true;
        return node.startsWith(prefix, idx + 1);
    }
}
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

QuadTree

A Quad-Tree is a tree data structure in which each internal node has exactly four children. Besides, each node has two attributes:

  • val: True if the node represents a grid of 1's or False if the node represents a grid of 0's.

  • isLeaf: True if the node is the leaf node on the tree or False if the node has four children.

      class Node {
          public boolean val;
          public boolean isLeaf;
          public Node topLeft;
          public Node topRight;
          public Node bottomLeft;
          public Node bottomRight;
      }
    


Geometry

Slope of two points

  • The slope formula is m=(y2-y1)/(x2-x1).

Distance between two points

  • d=√((x2 – x1)² + (y2 – y1)²).

log() in Java

  • Math.log(n) function in java returns the natural log of a no with base e. where e is 2.718.
//342. Power of Four
a = b^c -> c = log(a) base b
log(a) base b = c * log(b) base b
log(a) base b / log(b) base b = c
log(a) base b / 1 = c
therefore c = log(a) base b

log(a) base b = log(a) base e / log(b) base e, where e is 2.718
java uses base e for log function

BitWise Concepts

  • power of 2 nos will always have just one 1-bit and rest 0 bits

  • n-1 flips the rightmost 1 bit to 0 and flips all low bits 0 to 1.

  • n & n-1 == 0 , where n is the power of 2 or contains just one 1 bit and the rest 0 bits and n-1 contains just one 0 bit and the rest 1 bit

  • To check if the no is a power of two just do n & n-1 == 0

  • no, which is not a power of two in that n and n-1 both contain multiple 1-bit

  • 6 & 5 = 4, 0b110 & 0b101 = 0b100


Other Topics

Difference between int[] and Integer[] array


Why do we usually use || over |? What is the difference?

Computation of 2^n in O(logn) and O(1) time

  • It is useful in the case of subsequences where the subsequence count is 2^n.

  • binary exponentiation

1st method
2^n , 2^5
if n is odd
n * 2^(n-1) , 2 * 2^4
if n is even
n * n * 2^(n/2); , 2 * 2 * 2^2
we can compute 2^n in O(logn) time using a helper method using above logic.
  • through precomputation
2nd method
store the prev result and compute next
pows[0] = 1 ,2^0 = 1
pows[1] = pows[0] * 2, 2^1 = 2
pows[2] = pows[1] * 2, 2^2 = 4
it will take O(1) time, we need not compute 2^n everytime just return res at index n.

How to write 10^9+7 in Java?

int mod=(int)1e9+7;
  • 1e9 simply means (1) * (10^9)Typecast 1e9 to int since by default it is double => (int)1e9.

Find GCD of nos

//1st approach
int gcd(int a, int b) {
        return b==0?a:gcd(b,a%b);
    }

//2nd approach
int gcd(int a, int b)
    {
        // Everything divides 0
        if (a == 0)
            return b;
        if (b == 0)
            return a;

        // Base case
        if (a == b)
            return a;

        // a is greater
        if (a > b)
            return gcd(a - b, b);
        else
            return gcd(a, b - a);
    }

Validate a prime no

boolean isPrime(int n)
    {

        // Check if number is less than
        // equal to 1
        if (n <= 1)
            return false;

        // Check if number is 2
        else if (n == 2)
            return true;

        // Check if n is a multiple of 2
        else if (n % 2 == 0)
            return false;

        // If not, then just check the odds
        for (int i = 3; i <= Math.sqrt(n); i += 2) {
            if (n % i == 0)
                return false;
        }
        return true;
    }

Numbers Formula

The sum of n terms in AP

  • n/2[2a + (n – 1)d], whereais the first term &dis diff between the first & second terms

  • The sum of n natural numbers

  • sum = [n(n+1)]/2


Nth term in AP

  • Tn = a+ (n-1)d

  • where a is the base or min value and d is the difference between two consecutive AP.


How to assign the same value to multiple variables?

  • First, declare all the variables separately then assign values to them
int x, y, z;
x = y = z = int_max;
int newCurr, curr;
newCurr = curr = arr1[currIdx];

Difference between permutation and combination?

  • If the order is important, then the problem is related to permutation, and the possible number of samples will be, XY, YX, YZ, ZY, XZ, ZX. In this case, XY is distinct from the sample YX, YZ is distinct from the sample ZY and XZ is distinct from the sample ZX.

  • If the order is unnecessary, then the question is relevant to the combination, and the possible samples will be XY, YZ and ZX.

  • As you can see from the example above X can come at any place(0,1) in the list using permutation as the order is important and it will be treated as a distinct sample. XY & YX are distinct

  • But using combinations once X is part of the list regardless of its position in the list(0,1), It will be treated as the same sample.

  • XY & YX are the same samples.

  • that is why in permutation we always pick no from 0 to n for each position but in combinations, we pick no from start=0 to n, where the start is increasing by 1

  • ref - Difference Between Permutation and Combination

      //46. Permutations
      class Solution {
        public List<List<Integer>> permute(int[] nums) {
    
            List<List<Integer>> res = new ArrayList();
            backtrack(res, new ArrayList(), nums);
            return res;
        }
    
        private void backtrack(List<List<Integer>> res, List<Integer> temp, int[] nums) {
    
            if (temp.size() == nums.length)
                res.add(new ArrayList(temp));
            else {
                for (int i = 0; i < nums.length; i++) {
                    if (temp.contains(nums[i]))
                        continue;
                    temp.add(nums[i]);
                    backtrack(res, temp, nums);
                    temp.remove(temp.size() - 1);
                }
            }
        }
      }
      // 77. Combinations
      class Solution {
        public List<List<Integer>> combine(int n, int k) {
    
            List<List<Integer>> combs = new ArrayList();
            combine(combs, new ArrayList(), 1, n, k);
            return combs;
        }
    
        public static void combine(List<List<Integer>> combs, List<Integer> comb, int start, int n, int k) {
    
            if (k == 0) {
                combs.add(new ArrayList(comb));
                return;
            }
    
            for (int i = start; i <= n; i++) {
                comb.add(i);
                combine(combs, comb, i + 1, n, k - 1);
                comb.remove(comb.size() - 1);
            }
        }
      }
    

Base Conversions

  • to convert decimal to binary equivalent divide n by 2 till n is equal to 0.

  • Then use the remainder in reverse order to obtain the result.

  • if it is base 26 or base 14, use reminders 0..25, 0..13 equivalent to obtain the result.

  • N = 2002 decimal corresponds to BXZ in base 26

  • we can solve this from the back

  • Last digit we can obtain by taking mod 26 ie Z

  • Second last has 26 combinations at last place so we need to divide by 26 then take mod 26 ie X

  • Third last has 26*26 combinations before it so we need to divide by 26 then take mod 26 ie B

      N = 2002 corresponds to BXZ
      2002/26 -> 77 -> 77/26 -> 2 -> 2/26 -> 0
      using remainders
      2002 = 2*26^2 + 25 *26^1 + 0*26^0
      2002 = (B+1)*26^2 + (X+1)*26^1 + (Z+1)*26^0
      n = (B+1)*26^2 + (X+1)*26^1 + (Z+1)*26^0
      n-1 = (B+1)*26^2 + (X+1)*26^1 + Z
      (n-1)%26 = Z
      (n-1)/26 = (B+1)*26^1 + (X+1)*26^0
      and loop continues
    
  • ref - Number System and Base Conversions

  • 168. Excel Sheet Column Title


XOR operator

  • The XOR operator is denoted by a carrot (^) symbol. It takes two values and returns true if they are different; otherwise returns false. In binary, the true is represented by 1 and false is represented by 0.

      0^0 = 0
      1^1 = 0
      0^1 = 1
      1^0 = 1
      a^a = 0
      c=a^b, then a=c^b and b=a^c
    

Count No of bits in a number

private int countBit(int n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n >>= 1;
        }
        return res;
    }

//inbuilt method
Integer.bitCount(arr[i])

ASCII value of a character

  • In Java, the char variable stores the ASCII value of a character (a number between 0 and 127) rather than the character itself. ASCII values for lowercase alphabets range from 97 to 122. Uppercase alphabets have ASCII values ranging from 65 to 90.

  • The rest of the values from 0-127 contain special chars and number

// char index mapping, for 128 chars
    int last[] = new int[128]

Knight Move

  • a knight may move two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an L).

  • a knight can move in 4 directions up, bottom, left, right and their 2 sides

  • so total valid paths are 4*2= 8, it can reach 8 different places using just 1 jump.

        M[n][i][j] = paths(M, i + 2, j + 1, n - 1) % max + // down-right
                paths(M, i + 2, j - 1, n - 1) % max + // down-left
                paths(M, i - 2, j + 1, n - 1) % max + // up-right
                paths(M, i - 2, j - 1, n - 1) % max + // up-left
                paths(M, i - 1, j + 2, n - 1) % max + // right-top
                paths(M, i + 1, j + 2, n - 1) % max + // right-down
                paths(M, i - 1, j - 2, n - 1) % max + // left-up
                paths(M, i + 1, j - 2, n - 1) % max; // left+down

Conditions check

  • Never increment or decrement operators in the condition check.

  • It will always get executed without entering the block as the condition check happens always

//here i and j value will always increase 
//whether you enter the block or not
if(i++) {
//some computation
} else if(j++) {
//some computation
}

Important Algorithms

Floyd’s Cycle Finding Algorithm

  • Floyd cycle finding algorithm or hare-tortoise algorithm is used to find a loop in a linked list.

  • It uses two-pointers. fast ptr travels twice

  • the speed of slow ptr.

  • working

  • while traversing the list one of the two scenarios occur

  • fast ptr reaches null or end of the list

  • fast ptr becomes equal to or collides with slow ptr, which means there is a loop otherwise collision is not possible

//template
//287. Find the Duplicate Number
class Solution {
    public int findDuplicate(int[] nums) {

        int slow = 0, fast = 0;
        // first collision
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = 0;
        // second collision
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

Sliding Window Technique

  • this method is used to solve the problem in which we need to define the window or range in the input data(arrays or strings) and later move that window across the data to perform some operations.

  • It is used in algorithms like finding subarray with specific sum, finding the longest substring with unique characters or solving problems that require fixed-size windows to process elements efficiently.

  • Types and steps to solve it

  • Fixed-size sliding window

  • find the required window size like - K

  • compute the result of the 1st window by including the first k elements of data

  • then slide the window by 1 using a loop and keep computing result for each window

  • Variable-size sliding window

  • we increase our right ptr by 1 till the condition is true

  • For each step, if the condition does not match we shrink the window by increasing the left ptr

  • Again when the condition is satisfied we increase the right ptr by following step 1

  • we do these steps till we reach the end of the data (array)

  • How to identify sliding problems

  • these problems usually involve finding the maximum or minimum subarray or substring which satisfies a certain condition

  • the size of the subarray or substring will be given as k in some problems

  • These problems can be solved in O(n^2) using nested loops and in O(n) using a sliding window.

  • time complexity - O(n) or O(nlogn)

  • Use cases

  • Find the maximum sum of all subarrays of size k

    - It can be solved using a fixed-size sliding window

  • Smallest subarray with a sum greater than a given value

    - It can be solved using a variable-size sliding window
    - expand the window by increasing right ptr till the sum is less than k
    - when the sum is greater than k, update res with curr window size and keep shrinking the window till the sum is greater than k

  • Find a subarray with a given sum in an array of non-negative integers

    - It can be solved using a variable-size sliding window
    - add elements to the subarray till the sum is less than k
    - remove elements from the start of the subarray till the sum is greater than k

  • References

  • Sliding Window Technique


-the time complexities of various data structures

Arrays

  • Set, Check element at a particular index: O(1)

  • Searching: O(n) if the array is unsorted and O(log n) if the array is sorted and something like a binary search is used,

  • Similarly, Insert for arrays is basically Set as mentioned in the beginning

ArrayList

  • Add: Amortized O(1)

  • Remove: O(n)

  • Contains: O(n)

  • Size: O(1)

Linked List:

  • Inserting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traversing the LinkedList linearly.

  • Deleting: O(1), if done at the head, O(n) if anywhere else since we have to reach that position by traversing the LinkedList linearly.

  • Searching: O(n)

Doubly-Linked List:

  • Inserting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traversing the LinkedList linearly.

  • Deleting: O(1), if done at the head or tail, O(n) if anywhere else since we have to reach that position by traversing the LinkedList linearly.

  • Searching: O(n)

Stack

  • Push: O(1)

  • Pop: O(1)

  • Top: O(1)

  • Search (Something like lookup, as a special operation): O(n) (I guess so)

Queue/Deque/Circular Queue:

  • Insert: O(1)

  • Remove: O(1)

  • Size: O(1)

Binary Search Tree:

  • Insert, delete and search: Average case: O(log n), Worst Case: O(n)

Red-Black Tree:

  • Insert, delete and search: Average case: O(log n), Worst Case: O(log n)

Heap/PriorityQueue (min/max):

  • Find Min/Find Max: O(1)

  • Insert: O(log n)

  • Delete Min/Delete Max: O(log n)

  • Extract Min/Extract Max: O(log n)

  • Lookup, Delete (if at all provided): O(n), we will have to scan all the elements as they are not ordered like BST

HashMap/Hashtable/HashSet:

  • Insert/Delete: O(1) amortized

  • Re-size/hash: O(n)

  • Contains: O(1)

Revision

Map

  • create map

  • assign 0 if no value or increase it

  • add nos to map

  • check if the map contains certain key

  • check if the map contains a certain value

  • fetch value for a particular key