Search⌘ K
AI Features
Home
Courses
Algorithms for Coding Interviews in Java

Solution: Sparse Search

Explore effective methods to solve sparse search problems in Java, including brute force and a modified binary search that handles empty strings. Understand the time complexities and practical implementation details to improve your sorting and searching algorithms skills for coding interviews.

We'll cover the following...

Solution #1: Brute force

Java
class SparseSearch
{   
  public static int searchForString(String[] array, String target)
  {
    //traverse array
    for (int i = 0; i < array.length; i++) {
      //check if current value equals to target string
      if (array[i].equals(target)) {
        //return the index value
        return i;
      }
    }
    return -1;
  }
  public static void main(String args[]) 
  {
    String [] array = {"", "educative", "", "", "",  "hello", "", "learning", "world", "", "", ""};
    String [] targetArray = {"educative", "learning"};
    
    for(int i = 0; i < 2; i++) {
      System.out.println(targetArray[i] + ": " + searchForString(array, targetArray[i]));
    }
  }
}

In this solution, we traverse the entire array of strings and stop only if we find the target string or reach the end of the array.

Time complexity

The time complexity is the time it takes to traverse the entire array, i.e., O ...