Problem#
Given a sorted array of strings, which may contain empty strings (""), find the index of a given target string.
OR
Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string.
Examples#
Example 1#
1
2
3
4
5
6
7
Input:
array = [ "at" , "" , "" , "" , "ball" , "" , "" , "car" , "" , "" , "dad" , "" , "" ]
target = "ball"
Output:
4
Explanation:
The string "ball" is found at index 4.
Example 2#
1
2
3
4
5
6
7
Input:
array = [ "at" , "" , "" , "" , "" , "ball" , "car" , "" , "" , "dad" , "" , "" ]
target = "ballcar"
Output:
- 1
Explanation:
The string "ballcar" is not present in the array, so return - 1.
Constraints#
The array is sorted lexicographically.
The array may contain empty strings interspersed between non-empty strings.
The target string is a non-empty string.
Solution#
Method 1 - Linear Search#
The worst we can do is O(n) where we just do a linear search, but given string is sorted, we can use binary search, but some modification will be required.
Method 2 – Modified Binary Search (Divide and Conquer)#
Intuition#
Binary search is efficient for sorted arrays, but empty strings break direct comparison. The key idea is: when we hit an empty string, we search both sides to find the nearest non-empty string for comparison, then continue binary search as usual.
Approach#
Start with two pointers, left and right, at the bounds of the array.
While left <= right:
Compute mid = (left + right) // 2.
If array[mid] is empty, expand outwards from mid to find the closest non-empty string.
Compare the non-empty string at mid with the target:
- If equal, return mid.
- If less, move left to mid + 1.
- If greater, move right to mid - 1.
If not found, return -1.
Code#
Cpp
Go
Java
Kotlin
Python
Rust
Typescript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public :
int SearchString(const std:: vector< std:: string>& arr, const std:: string& target) {
int left = 0 ;
int right = arr.size() - 1 ;
while (left <= right) {
int mid = left + (right - left) / 2 ;
int orig_mid = mid;
// Find closest non-empty string
while (mid >= left && arr[mid] == "" ) {
-- mid;
}
if (mid < left) {
mid = orig_mid + 1 ;
while (mid <= right && arr[mid] == "" ) {
++ mid;
}
if (mid > right) {
return - 1 ;
}
}
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = orig_mid + 1 ;
} else {
right = mid - 1 ;
}
}
return - 1 ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func SearchString (arr []string , target string ) int {
left , right := 0 , len(arr )- 1
for left <= right {
mid := left + (right - left )/ 2
origMid := mid
for mid >= left && arr [mid ] == "" {
mid --
}
if mid < left {
mid = origMid + 1
for mid <= right && arr [mid ] == "" {
mid ++
}
if mid > right {
return - 1
}
}
if arr [mid ] == target {
return mid
}
if arr [mid ] < target {
left = origMid + 1
} else {
right = mid - 1
}
}
return - 1
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Solution {
public int searchString (String[] arr, String target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
int origMid = mid;
while (mid >= left && arr[ mid] .isEmpty ()) {
mid-- ;
}
if (mid < left) {
mid = origMid + 1;
while (mid <= right && arr[ mid] .isEmpty ()) {
mid++ ;
}
if (mid > right) {
return - 1;
}
}
if (arr[ mid] .equals (target)) {
return mid;
}
if (arr[ mid] .compareTo (target) < 0) {
left = origMid + 1;
} else {
right = mid - 1;
}
}
return - 1;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
fun searchString (arr: List<String>, target: String): Int {
var left = 0
var right = arr.size - 1
while (left <= right) {
var mid = left + (right - left) / 2
val origMid = mid
while (mid >= left && arr[mid].isEmpty()) {
mid--
}
if (mid < left) {
mid = origMid + 1
while (mid <= right && arr[mid].isEmpty()) {
mid++
}
if (mid > right) {
return -1
}
}
if (arr[mid] == target) {
return mid
}
if (arr[mid] < target) {
left = origMid + 1
} else {
right = mid - 1
}
}
return -1
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
from typing import List
class Solution :
def search_string (self, arr: List[str], target: str) -> int:
left, right = 0 , len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
orig_mid = mid
while mid >= left and arr[mid] == "" :
mid -= 1
if mid < left:
mid = orig_mid + 1
while mid <= right and arr[mid] == "" :
mid += 1
if mid > right:
return - 1
if arr[mid] == target:
return mid
if arr[mid] < target:
left = orig_mid + 1
else :
right = mid - 1
return - 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
impl Solution {
pub fn search_string (arr: & [String], target: & str ) -> i32 {
let (mut left, mut right) = (0 , arr.len() as i32 - 1 );
while left <= right {
let mut mid = left + (right - left) / 2 ;
let orig_mid = mid;
while mid >= left && arr[mid as usize ] == "" {
mid -= 1 ;
}
if mid < left {
mid = orig_mid + 1 ;
while mid <= right && arr[mid as usize ] == "" {
mid += 1 ;
}
if mid > right {
return - 1 ;
}
}
if arr[mid as usize ] == target {
return mid as i32 ;
}
if arr[mid as usize ] < target {
left = orig_mid + 1 ;
} else {
right = mid - 1 ;
}
}
- 1
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
searchString (arr : string [], target : string ): number {
let left = 0 ;
let right = arr .length - 1 ;
while (left <= right ) {
let mid = left + Math.floor ((right - left ) / 2 );
const origMid = mid ;
while (mid >= left && arr [mid ] === "" ) {
mid -- ;
}
if (mid < left ) {
mid = origMid + 1 ;
while (mid <= right && arr [mid ] === "" ) {
mid ++ ;
}
if (mid > right ) {
return - 1 ;
}
}
if (arr [mid ] === target ) {
return mid ;
}
if (arr [mid ] < target ) {
left = origMid + 1 ;
} else {
right = mid - 1 ;
}
}
return - 1 ;
}
}
Complexity#
⏰ Time complexity: O(n) in the worst case, because if the array is mostly empty strings, we may have to scan linearly to find non-empty strings. In the average case, binary search dominates, so it’s closer to O(log n).
🧺 Space complexity: O(1), since only a constant amount of extra space is used for pointers and indices.