Tech Tutorials

For each prime number mark all its multiple as non-prime in the table. That's what make this algorithm efficient, for example if 2 is a prime number then none of its multiple 4, 6, 8… is going to be a prime number. Same way if 3 is a prime number then none of its multiple 6, 9, 12, 15.. is going to be a prime number.

After the marking is done, which ever numbers are still unmarked are prime numbers.

For example, if we have to find prime numbers in the range 1-10 then we can visualize it as given here-

For 2, mark all the multiples of 2 as not prime-

For 3, mark all the multiples of 3 as not prime-

Same way for next numbers 5 and 7. At the end you will be left with the numbers that are prime. Note, that 1 is also not considered as a prime number that will be taken care of in the program by starting the loop from 2.

Sieve of Eratosthenes Java program

import java.util.Arrays;
import java.util.Scanner;

public class EratosthenesSieve {
  private static void getPrimes(int n) {
    // table to keep track of prime or not
    boolean[] primeTable = new boolean[n+1];
    // intially mark all of the array element as true
    Arrays.fill(primeTable, true);
    for(int i = 2; i <= n; i++) {
      // still true means it is a prime number
      if(primeTable[i]) {
        // multiples of i should be marked as not prime
        for(int j = i * i; j <= n; j = j+i) {
          primeTable[j] = false;
        }
      }
    }
    // print all the prime numbers which'll be the 
    // the elements in the array still marked as true
    // printing can also be done in the above for loop itself
    // after the if condition block
    for(int i = 2; i <= n; i++) {
      if(primeTable[i]) {
        System.out.print(i + " ");
      }
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the number for range: ");
    int n = sc.nextInt();
    getPrimes(n);
    sc.close();
  }

}

Output

Enter the number for range: 
50
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47

Time and space complexity of Sieve of Eratosthenes algorithm

Outer loop runs n times.

Inner loop runs n/i times for i = 2, 3, 5…. when i = 2, the internal loop will be executed n/2 times. For i = 3, it'll be executed n/3 times. For i = 5, it'll be executed n/5 times, and so on. This results in the time complexity of O(log(log n))

Thus, the overall time complexity is O(n X log(log n))

We need an array of length n+1 for marking the non-primes so the space complexity is O(n).

That's all for this topic Java Program - Sieve of Eratosthenes to Find Prime Numbers. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page

Related Topics

You may also like-

Weighted Graph Adjacency Representation - Java Program

In the article Graph Adjacency Representation - Java Program, we saw how to represent an unweighted graph using adjacency list or adjacency matrix. In this post we'll see what is a weighted graph and how to represent a weighted graph using adjacency list or adjacency matrix in Java.

Weighted graph

In a weighted graph, numerical values called weights are assigned to edges. These weights may represent distance, cost, time etc. For example, if vertices in a graph represent cities, then weight of the edges may mean the distances between the cities, cost t travel between cities or time it takes to drive between cities.

Weighted graph representation using adjacency matrix

An adjacency matrix is a 2-D array in which weight of the edge is used as elements to indicate whether an edge is present between two vertices or not. For example, adjMat[i][j] stores the weight of the edge between i and j vertices.

If the edge is not present it is represented by value as infinity or zero for that cell in the matrix.

For the above image which represents an undirected weighted graph the adjacency matrix can be visualized as shown below. An undirected graph means that the edges don't have direction and you can traverse both ways. You can go from vertex A to vertex B or from vertex B to vertex A.

Weighted Undirected Graph adjacency matrix Java Program

public class WtGraphAdjMatrix {
  private int vertices;
  private int[][] adjMatrix;

  WtGraphAdjMatrix(int vertices){
    this.vertices = vertices;
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination, int weight) {
    if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = weight;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = weight;
  }
  
  public void printGraph() {
    for(int i = 0; i < adjMatrix.length; i++) {
      for(int j = 0; j < adjMatrix[0].length; j++) {
        System.out.print(adjMatrix[i][j] + "\t");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    WtGraphAdjMatrix graph = new WtGraphAdjMatrix(5);
    graph.addEdge(0, 1, 5); //A-B
    graph.addEdge(0, 2, 10); //A-C
    graph.addEdge(0, 4, 7); //A-E
    graph.addEdge(2, 3, 15); //C-D
    graph.addEdge(3, 4, 8); //D-E


    graph.printGraph();
  }
}

Output

0   5	  10	0	  7	
5	  0	  0	  0	  0	
10  0	  0	  15  0	
0	  0	  15	0	  8	
7	  0	  0	  8	  0

Weighted Directed Graph adjacency matrix Java Program

In a directed graph you can traverse in only one direction. The allowed direction is shown with an arrow at the end of the edge.

Adjacency matrix for the above weighted directed graph can be visualized as-

Weighted Directed Graph Adjacency Matrix

Java code for the directed Graph adjacency matrix requires just commenting a single line in the above code for the undirected graph, the reverse link in the matrix.

public void addEdge(int source, int destination, int weight) {
  if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
    System.out.println("Invalid edge addition");
    return;
  }
  adjMatrix[source][destination] = weight;
  // For undirected graph reverse setting also required
  //adjMatrix[destination][source] = weight;
}

If you run the code after commenting the line, output is-

0   5	  10	0	  7	
0	  0	  0	  0	  0	
0	  0	  0	  15	0	
0	  0	  0	  0	  8	
0	  0	  0	  0	  0

Weighted Graph representation using adjacency list

Another way to represent a weighted graph is using an adjacency list which is an array of lists or a list of lists. Each vertex has an associated list storing all the adjacent vertices. In this associated list each element will have two values connected vertex and the weight between two vertices.

Adjacency list for the above weighted undirected graph can be visualized as-

Weighted Undirected Graph adjacency list Java Program

In the Java program Map and List collections are used to represent adjacency list. Each map key has an associated list to show the adjacent vertices. There is also a class named Edge that encapsulates the adjacent vertex and weight fields.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class WtGraphAdjList {
  int vertices;
  Map<String, List<Edge>> adjList;
  static class Edge{
    String destination;
    int weight;
    Edge(String destination, int weight){
      this.destination = destination;
      this.weight = weight;
    }
  }
  
  WtGraphAdjList(int vertices){
    this.vertices = vertices;
    adjList = new HashMap<>();
  }
  void addEdge(String source, String destination, int weight) {

    adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
    // For undirected graph
    adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
  }
  
  public void printGraph() {
    for(Map.Entry<String, List<Edge>> es : adjList.entrySet()) {
      System.out.print("Vertex " + es.getKey() + " connects to: ");
      List<Edge> list = es.getValue();
      for (Edge e : list) {
        System.out.print("[" + e.destination + " with weight " + e.weight + "] ");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    WtGraphAdjList graph = new WtGraphAdjList(5);
    graph.addEdge("A", "B", 5);
    graph.addEdge("A", "C", 10);
    graph.addEdge("A", "E", 7);
    graph.addEdge("C", "D", 15);
    graph.addEdge("D", "E", 8);
    
    graph.printGraph();
  }
}

Output

Vertex A connects to: [B with weight 5] [C with weight 10] [E with weight 7] 
Vertex B connects to: [A with weight 5] 
Vertex C connects to: [A with weight 10] [D with weight 15] 
Vertex D connects to: [C with weight 15] [E with weight 8] 
Vertex E connects to: [A with weight 7] [D with weight 8]

Weighted Directed Graph adjacency list Java Program

In case of directed graph, you can traverse in only one direction.

Java code for the directed Graph adjacency matrix requires just commenting the line that creates a reverse link in the list.

void addEdge(String source, String destination, int weight) {
  adjList.computeIfAbsent(source, k->new ArrayList<>()).add(new Edge(destination, weight));
  // For undirected graph
  //adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(new Edge(source, weight));
}

With that change the output is-

Vertex A connects to: [B with weight 5] [C with weight 10] [E with weight 7] 
Vertex C connects to: [D with weight 15] 
Vertex D connects to: [E with weight 8]

That's all for this topic Weighted Graph Adjacency Representation - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page

Related Topics

You may also like-

Friday, October 10, 2025

Graph Adjacency Representation - Java Program

In this post we'll see how to represent a graph using adjacency list and adjacency matrix. Here we'll see representation for the unweighted graph.

Graph is a data structure which is similar to tree and has nodes and edges. Nodes are generally called vertices when it comes to graph.

If you want to see how to represent a weighted graph using adjacency list and adjacency matrix, check this post- Weighted Graph Adjacency Representation - Java Program

What is adjacency

The vertices in a graph are said to be adjacent to one another if they are connected directly by a single edge.

The above graph has 5 vertices (A, B, C, D, E) and 5 edges. The circles represent the vertices and the lines connecting them are edges. In the above figure vertex A is adjacent to B and C but A is not adjacent to vertex D.

A binary tree has a fixed structure; each node has a maximum of two children. Graph doesn't have that kind of fixed structure, in a graph each vertex may be connected to an arbitrary number of other vertices. In the above vertex A is connected to B, C and E vertices.

Because of this kind of structure, to represent a graph two methods are generally used-

Adjacency matrix
Adjacency List

Graph representation using adjacency matrix

An adjacency matrix is a 2-D array in which 0 and 1 are used as elements to indicate whether an edge is present between two vertices or not.

An edge between two vertices is marked using 1
If there is no edge between two vertices then 0 is used

If a graph has n vertices, then adjacency matrix also has n rows and n columns (n X n array).

For the above image which represents an undirected graph the adjacency matrix can be visualized as shown below. An undirected graph means that the edges don't have direction and you can traverse both ways. You can go from vertex A to vertex B or from vertex B to vertex A.

Adjacency matrix representation is easy to implement and efficient in terms of accessing any element, but it is less space efficient because you are storing information about all possible edges rather than just actual connections (adjacency list stores only actual connections).

Undirected Graph adjacency matrix Java Program

public class GraphAdjMatrix {
  private int vertices;
  private int[][] adjMatrix;

  GraphAdjMatrix(int vertices){
    this.vertices = vertices;
    // matrix having same row and columns as vertices
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination) {
    if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = 1;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 1;
  }
  
  public void printGraph() {
    for(int i = 0; i < adjMatrix.length; i++) {
      for(int j = 0; j < adjMatrix[0].length; j++) {
        System.out.print(adjMatrix[i][j] + "\t");
      }
      System.out.println();
    }
  }
  
  public static void main(String[] args) {
    GraphAdjMatrix graph = new GraphAdjMatrix(5);
    graph.addEdge(0, 1); //A-B
    graph.addEdge(0, 2); //A-C
    graph.addEdge(0, 4); //A-E
    graph.addEdge(2, 3); //C-D
    graph.addEdge(3, 4); //D-E

    graph.printGraph();

  }
}

Output

Directed Graph adjacency matrix Java Program

In a directed graph you can traverse in only one direction. The allowed direction is shown with an arrow at the end of the edge.

Adjacency matrix for the above directed graph can be visualized as-

Java code for the directed Graph adjacency matrix requires just commenting a single line in the above code for the undirected graph, the reverse link in the matrix.

public void addEdge(int source, int destination) {
  if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
    System.out.println("Invalid edge addition");
    return;
  }
  adjMatrix[source][destination] = 1;
  // For undirected graph reverse setting also required
  //adjMatrix[destination][source] = 1;
}

With that the output is-

Graph representation using adjacency list

Another way to represent a graph is using an adjacency list which is an array of lists or a list of lists. Each vertex in a list shows all the adjacent vertices as another list, linked to this vertex.

Adjacency list for the above undirected graph can be visualized as-

Undirected Graph adjacency list Java Program

In the Java program Map and List collections are used to represent adjacency list. Each map key has an associated list to show the adjacent vertices.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class GraphAdjList {
  int vertices;
  Map<String, List<String>> adjList;
  
  GraphAdjList(int vertices){
    this.vertices = vertices;
    adjList = new HashMap<>();

  }
  
  public void addEdge(String source, String destination) {
    adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
    // For undirected graph
    adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
  }
  
  public void printGraph() {
    for(Map.Entry<String, List<String>> es :adjList.entrySet()) {
      System.out.print("Vertex " + es.getKey() + " connects to: ");
      List<String> list = es.getValue();
      for (String s : list) {
        System.out.print("[" + s + "] ");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    GraphAdjList graph = new GraphAdjList(5);
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("A", "E");
    graph.addEdge("C", "D");
    graph.addEdge("D", "E");
    
    graph.printGraph();
  }
}

Output

Vertex A connects to: [B] [C] [E] 
Vertex B connects to: [A] 
Vertex C connects to: [A] [D] 
Vertex D connects to: [C] [E] 
Vertex E connects to: [A] [D]

As you can see with adjacency list you store only the actual connections so it is more space efficient.

Directed Graph adjacency list Java Program

In case of directed graph, you can traverse in only one direction.

Adjacency list for the above directed graph can be visualized as-

Java code for the directed Graph adjacency matrix requires just commenting the line that creates a reverse link in the list.

public void addEdge(String source, String destination) {
  adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
  // For undirected graph
  //adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
}

With that change the output is-

Vertex A connects to: [B] [C] [E] 
Vertex C connects to: [D] 
Vertex D connects to: [E]

That's all for this topic Graph Adjacency Representation - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Thursday, October 9, 2025

Java Stream - Collectors.partitioningBy() With Examples

If you want to partition stream elements into two groups as per the given condition you can do that using partitioningBy() method of the java.util.stream.Collectors class.

Collectors.partitioningBy() method in Java

Collectors.partitioningBy() method partitions the input elements according to the passed Predicate argument and organizes them into a Map<Boolean, List<T>>. As you can notice the key in the Map is of type Boolean because the two keys used are “false” and “true” to map the input elements.

false- To map the input elements that doesn't pass the condition
true- To map the input elements that pass the condition

There are two overloaded partitioningBy() method with Syntax as given below-

Collector<T,?,Map<Boolean, List<T>>> partitioningBy(Predicate<? super T> predicate)- Partitions the stream elements according to the passed Predicate.
Collector<T,?,Map<Boolean,D>> partitioningBy(Predicate<? super T> predicate, Collector<? super T,A,D> downstream)- In this variant there is a Second argument of type Collector which reduces the values in each partition and organizes them into a Map<Boolean, D> whose values are the result of the downstream reduction.

Collectors.partitioningBy() Java examples

1. In this Collectors.partitioningBy() example we'll use it to partition a list of integers to return a map of even and odd numbers.

import java.util.Arrays;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

public class CollectorsPartitioning {

  public static void main(String[] args) {
    List<Integer> listOfNumbers = Arrays.asList(5,9,14,19,47,56,72,89,90,18);
      Map<Boolean, List<Integer>> numbers = listOfNumbers.stream()
                                 .collect(Collectors.partitioningBy(n -> n%2 == 0));
      // When key false - returns list with odd numbers
      System.out.println("Odd Numbers- " + numbers.get(false));
      // When key true - returns list with even numbers
      System.out.println("Even Numbers- " + numbers.get(true));
  }
}

Output

Odd Numbers- [5, 9, 19, 47, 89]
Even Numbers- [14, 56, 72, 90, 18]

2. Partition a List of Employee into those who earn more than 8000 and those who don’t using Collectors.partitioningBy() method in Java.

Employee Class

public class Employee {
  private String empId;
  private int age;
  private String name;
  private char gender;
  private int salary;
  Employee(String empId, int age, String name, char gender, int salary){
    this.empId = empId;
    this.age = age;
    this.name = name;
    this.gender = gender;
    this.salary = salary;
  }
  public String getEmpId() {
    return empId;
  }

  public int getAge() {
    return age;
  }

  public String getName() {
    return name;
  }

  public char getGender() {
    return gender;
  }

  public int getSalary() {
    return salary;
  }
  @Override
  public String toString() {
      return "Emp Id: " +  getEmpId() + " Name: " + getName() + " Age: " + getAge();
  }
}

public class CollectorsPartitioning {

  public static void main(String[] args) {
    List<Employee> empList = Arrays.asList(new Employee("E001", 40, "Ram", 'M', 5000), 
                new Employee("E002", 35, "Shelly", 'F', 8000), 
                new Employee("E003", 24, "Mark", 'M', 9000), 
                new Employee("E004", 37, "Ritu", 'F', 11000),
                new Employee("E005", 32, "Anuj", 'M', 6000), 
        new Employee("E006", 28, "Amy", 'F', 14000));
      Map<Boolean, List<Employee>> numbers = empList.stream()
                                 .collect(Collectors.partitioningBy(e -> e.getSalary() > 8000));
      // When key false - employee with salary <= 8000
      System.out.println("Employees with Salary less than 8000- " + numbers.get(false));
      // When key true - employee with salary > 8000
      System.out.println("Employees with Salary greater than 8000- " + numbers.get(true));
  }
}

Output

Employees with Salary less than 8000- [Emp Id: E001 Name: Ram Age: 40, Emp Id: E002 Name: Shelly Age: 35, Emp Id: E005 Name: Anuj Age: 32]
Employees with Salary greater than 8000- [Emp Id: E003 Name: Mark Age: 24, Emp Id: E004 Name: Ritu Age: 37, Emp Id: E006 Name: Amy Age: 28]

3. In the second example we got the Employees partitioned into groups as per the condition salary greater than 8000 or not. Suppose you want the count of employees in each partitioned group, in that scenario you can use the Collectors.partitioningBy() method with two arguments and pass the second argument which is a counting Collector in this case.

public class CollectorsPartitioning {

  public static void main(String[] args) {
    List<Employee> empList = Arrays.asList(new Employee("E001", 40, "Ram", 'M', 5000), 
                new Employee("E002", 35, "Shelly", 'F', 8000), 
                new Employee("E003", 24, "Mark", 'M', 9000), 
                new Employee("E004", 37, "Ritu", 'F', 11000),
                new Employee("E005", 32, "Anuj", 'M', 6000), 
        new Employee("E006", 28, "Amy", 'F', 14000));
      Map<Boolean, Long> numbers = empList.stream()
                                 .collect(Collectors.partitioningBy(e -> e.getSalary() > 8000, Collectors.counting()));
      // When key false - employee with salary <= 8000
      System.out.println("Count of employees with Salary less than 8000- " + numbers.get(false));
      // When key true - employee with salary > 8000
      System.out.println("Count of employees with Salary greater than 8000- " + numbers.get(true));
  }
}

Output

Count of employees with Salary less than 8000- 3
Count of employees with Salary greater than 8000- 3

That's all for this topic Java Stream - Collectors.partitioningBy() With Examples. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Advanced Tutorial Page

Related Topics

You may also like-

Z Algorithm For Pattern Search - Java Program

In this post we'll see how to write a Java program for Z algorithm which is used for pattern searching. In order to efficiently do searching in linear time i.e. O(n + m) there is pre-computation step in the Z algorithm to compute a Z array

Z array in the Z algorithm

For a string of length n, a Z array is also created of the same length and each index in the Z array i.e. Z[i] stores the length of the longest substring starting from i that is also a prefix of the string. Which means each index contains the length of the substring from i onward that matches the beginning of the String.

For example, if the String is "aabcbaab" then the computed Z array is-

[0, 1, 0, 0, 0, 3, 1, 0]

Z[0] is always 0 by convention.

Z[1] is 1 because from position one, single character matches from the beginning of the string.

Z[2], Z[3], Z[4] are having value as 0 as 'b', 'c' or 'b' doesn't match with 'a'.

Z[5] has value 3 because from index 5 we have a substring of length 3 'aab' that matches the prefix 'aab'.

Z[6] is 1 because there is only a single character match.

Z[7] is 0 because there is no match.

Optimization while calculating Z array

Rather than using nested loops, two pointers l and r are used to represent the borders of the current substring that matches the prefix of the string.

l is the start index of that substring and r is the end index of the substring.

In the String "aabcbaab", for index 5 we have a substring of length 3 matching the prefix of the same string.

With the help of these 2 pointers, it reuses previously computed values to avoid redundant comparisons, achieving O(n) time complexity. There are the following two scenarios-

When current index i is within the range of l and r, for example, if current index i is 6 then it is with in the range of l and r when l is 5 and r is 7. Then Z[i] = min(r - i + 1, z[i - l]) because str[i] matches with str[i - l] for at least right-i+1 characters. So, you can start comparison after those characters.

When current index i is greater than r which means it is outside the range of l and r then reset l and r to reflect current substring.

Note that r keeps moving only forward, it never decreases which avoids redundant comparisons.

Here is the Z function that computes the Z array.

public static int[] computeZArray(String s) {
  int len = s.length();
  int[] z = new int[len];
  // it’ll anyway initialize to 0, just to show it explicitly
  z[0] = 0;
  int l = 0, r = 0;
  for(int i = 1; i < len; i++) {
    if(i <= r) {
      z[i] = Math.min(r - i + 1, z[i - l]);
    }
    while((i+z[i]) < len && s.charAt(z[i]) == s.charAt(i + z[i])) {
      z[i]++;
    }
    if(i + z[i] - 1 > r) {
      l = i;
      r = i + z[i] - 1;
    }
  }
  return z;
}

Z algorithm for pattern searching - Java Program

If the above precomputation of Z array is clear then there is not much left in the Z algorithm for pattern searching. Though there is one more pre-processing step here which is to combine the text and the pattern string using a character that doesn't appear in the string. In the program "$" is used to combine the strings.

Combined string = pattern + "$" + text

This combined string is passed to compute the Z array.

The idea here is; if pattern is considered the prefix and same pattern exists somewhere else in the text, then with in the Z array you should have the index that has the value equalling pattern length.

Here is the code snippet that shows the same logic-

for (int i = patLength + 1; i < z.length; i++) {
  if (z[i] == patLength) {
    // Match found at this index in text
    result.add(i - patLength - 1); 
  }
}

Here is the complete Z algorithm pattern searching program in Java.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ZAlgorithm {

  public static void main(String[] args) {
    String str = "aabcbaab";
    String pattern = "aab";
    //int[] z = computeZArray(str);
    //System.out.println(Arrays.toString(z));
    List<Integer>result = findPattern(pattern, str);
    System.out.println("Pattern found at " + result);
  }
  
  public static int[] computeZArray(String s) {
    int len = s.length();
    int[] z = new int[len];
    z[0] = 0;
    int l = 0, r = 0;
    for(int i = 1; i < len; i++) {
      if(i <= r) {
        z[i] = Math.min(r - i + 1, z[i - l]);
      }
      while((i+z[i]) < len && s.charAt(z[i]) == s.charAt(i + z[i])) {
        z[i]++;
      }
      if(i + z[i] - 1 > r) {
        l = i;
        r = i + z[i] - 1;
      }
    }
    return z;
  }
  
  // Finds all occurrences of pattern String 
  // in the text using Z-algorithm
  public static List<Integer> findPattern(String pattern, String text) {
    String concat = pattern + "$" + text;
    int[] z = computeZArray(concat);
    System.out.println("Computed Z array- " + Arrays.toString(z));
    List<Integer> result = new ArrayList<>();
    int patLength = pattern.length();

    for (int i = patLength + 1; i < z.length; i++) {
      if (z[i] == patLength) {
        // Match found at this index in text
        result.add(i - patLength - 1); 
      }
    }
    return result;
  }
}

Output

Computed Z array- [0, 1, 0, 0, 3, 1, 0, 0, 0, 3, 1, 0]
Pattern found at [0, 5]

Time and space complexity of Z algorithm

If original string is of length n and pattern string is of length m then Z array computation is O(n + m) because both pattern string and original string are combined.

Pattern searching is done only for length of the original string so that is O(n).

So, the total time complexity is O(n + m) + O(n) which can be termed as O(n + m).

Auxiliary space is needed for creating a new combined string of size m + 1 + n and Z array is also created of same m + 1 + n length. So, the space complexity is also O(n + m).

That's all for this topic Z Algorithm For Pattern Search - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tuesday, October 7, 2025

Two Sum - Elements in Array With Given Sum Java Program

In the post Two Sum - Array Indices With Given Sum Java Program we saw how to write Java program for the given problem statement to find the indices. There is another variant of two sum problem where you may be asked to find all the pairs in the array that add up to the given target. So, rather than indices of the elements in the array you need to find the numbers itself that add up to the target.

For example:

1. Input: int[] arr = {4, 7, 5, 6}, target = 10
Output: (4, 6)

2. Input: int[] arr = {4, 6, 5, -10, 8, 5, 5,20}, target = 10
Output: (-10,20) (4,6) (5,5)

3. Input: int[] arr = {18, 12, 4, 2, 1, 5, 10}, target = 6
Output: (1,5) (2,4)

Java program for this problem statement can be written using one of the following approaches.

Using nested loops which is not a very efficient solution.
Using HashSet which is more efficient.
By sorting the array and using two pointers.

1. Find pairs in an array using nested loops - Java Program

If you write the program, to find all the pair of numbers in an array that add up to the given target, using nested loops then you will have an outer loop that traverses through the array elements and an inner loop which starts from one more than the current outer loop iterator value.

public class PairsInArray {

  public static void main(String[] args) {
    int[] numArr = new int[] {4, 6, 5, -10, 8, 5, 5,20};
    int target = 10;
    findThePairs(numArr, target);
  }
  
  // With two loops 
  private static void findThePairs(int inputArray[], int target){
    String result = "";
    int len = inputArray.length;
    for(int i = 0; i < len; i++) {
      for(int j = i+1; j <len;j++) {
        int sum = inputArray[i] + inputArray[j];
        if(sum == target) {
          result = result + "(" + inputArray[i] + "," + inputArray[j] + ") ";
          break;
        }      
      }
    }
    // display all the pairs
    System.out.println(result);
  }
}

Output

(4,6) (5,5) (-10,20) (5,5)

Time and space complexity with nested loops

Since there are two loops, outer loop traversing all the elements and inner loop traversing through rest of the array to find another number to get the sum as target. Thus, the time complexity is O(n²).

Space complexity is O(1) as no auxiliary space is required with this approach.

2. Find pairs in array using HashSet - Java Program

In this approach HashSet is used to store array elements. You need to traverse array only once so only single loop is needed, in each iteration for the current element you calculate its difference with the target. Then, check in the Set to verify if there is any element already stored in the Set which is equal to this difference. If yes, that is the pair you are looking for.

public class PairsInArray {

  public static void main(String[] args) {
    int[] numArr = new int[] {4, 6, 5, -10, 8, 5, 5,20};
    int target = 10;
    findPairSet(numArr, target);
  }
  
  // Using HashSet
  public static void findPairSet(int inputArray[], int target) {
    String result = "";
    Set<Integer> pairSet = new HashSet<Integer>();
    for(int i = 0; i < inputArray.length; i++) {
      int c = target - inputArray[i];
      if(pairSet.contains(c)) {
        result = result +  "("+c + ", " + inputArray[i] + ")";
      }
      pairSet.add(inputArray[i]);
      
    }
    System.out.println(result);
  }
}

Output

(4, 6)(5, 5)(5, 5)(-10, 20)

As you can see from the output, with this approach and with nested loops you may have elements that are used more than once, extra logic is needed to take care of this. With two pointers approach you don't have this issue.

Time and space complexity with HashSet approach

Since there is only a single loop iterating the array and HashSet operations to check for value and to add elements are considered O(1) so the time complexity of this solution is O(n).

Extra space for HashSet is needed, which in worst case may store all the elements of the array so the space complexity is O(n).

3. Find pairs in array using Two pointers - Java Program

In this solution two pointer logic is used where the left pointer starts from the beginning of the array and the right pointer starts from the end of the array. Then you need to check if arr[left] + arr[right] = target, if yes you have got a pair, otherwise based on whether the sum is less than or greater than the target, you need to increment left pointer or decrement right pointer.

Array should be sorted to make it work with the two-pointer approach so that is the pre-computation required with this approach.

public class PairsInArray {

  public static void main(String[] args) {
    int[] numArr = new int[] {4, 6, 5, -10, 8, 5, 5,20};
    int target = 10;
    findPairsTwoPointer(numArr, target);
  }
  
  // With one loop - 2 pointer
  private static void findPairsTwoPointer(int inputArray[], int target){
    String result = "";
    int len = inputArray.length;
    int low = 0;
    int high = len - 1;
    // sort the array
    Arrays.sort(inputArray);
    
    while(low < high) {
      if(inputArray[low] + inputArray[high] == target){
        result = result + " (" + inputArray[low] + "," + inputArray[high] + ")";
        low++;
        high--;
            
      }else if(inputArray[low] + inputArray[high] < target){
        low++;             
      }else{
        high--;
      }
    }
    
    System.out.println(result);
  }
}

Output

(-10,20) (4,6) (5,5)

Time and space complexity with Two-pointer approach

Sorting the array is O(n log n), then traversing the loop is O(n) operation so the total time complexity is O(n log n) + O(n). Which simplifies to O(n log n).

As extra space only some variables are initialized which is not significant so the space complexity is O(1).

This is an efficient solution if array is already sorted.

That's all for this topic Two Sum - Elements in Array With Given Sum Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-