Find Smallest Letter Greater Than Target - Java Solution

🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.

▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube

▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube

1. Introduction

In this blog post, we'll explore a problem that involves searching for the smallest letter greater than a given target in a sorted array of lowercase letters. This problem is a variant of binary search and demonstrates how binary search can be adapted for circularly sorted arrays.

Problem

Given an array of lowercase letters sorted in ascending order, and a target letter, find the smallest letter in the array that is greater than the target. The letters wrap around, meaning that if the target is greater than all the letters in the array, the search wraps around to the beginning of the array.

Example 1:

Input: letters = ["d", "h", "l"], target = "a"

Output: "d"

Example 2:

Input: letters = ["d", "h", "l"], target = "d"

Output: "h"

Example 3:

Input: letters = ["d", "h", "l"], target = "f"

Output: "h"

Example 4:

Input: letters = ["d", "h", "l"], target = "j"

Output: "l"

Example 5:

Input: letters = ["d", "h", "l"], target = "n"

Output: "d"

2. Solution Steps

1. Use binary search to find the smallest letter greater than the target.

2. If the target is greater than or equal to the last element in the array, return the first element.

3. If the target is found or the search space is exhausted, return the element just after the last mid-point.

4. Adjust the binary search to wrap around the array if necessary.

3. Code Program

public class Solution {

    // Main method for testing
    public static void main(String[] args) {
        char[] letters1 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'a': " + nextGreatestLetter(letters1, 'a'));

        char[] letters2 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'd': " + nextGreatestLetter(letters2, 'd'));

        char[] letters3 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'f': " + nextGreatestLetter(letters3, 'f'));

        char[] letters4 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'j': " + nextGreatestLetter(letters4, 'j'));

        char[] letters5 = {'d', 'h', 'l'};
        System.out.println("Smallest letter greater than 'n': " + nextGreatestLetter(letters5, 'n'));
    }

    // Method to find the smallest letter greater than the target
    public static char nextGreatestLetter(char[] letters, char target) {
        int start = 0, end = letters.length - 1;

        while (start <= end) {
            int mid = start + (end - start) / 2;

            if (letters[mid] <= target) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return letters[start % letters.length];
    }
}

Output:

Smallest letter greater than 'a': d
Smallest letter greater than 'd': h
Smallest letter greater than 'f': h
Smallest letter greater than 'j': l
Smallest letter greater than 'n': d

Explanation:

The nextGreatestLetter method performs a binary search to find the smallest letter greater than the target. If the target letter is found or if we reach the end of the array, the method returns the next letter in the sorted array, wrapping around if necessary. 

For example, for the input array ['d', 'h', 'l'] and target 'f', the method returns 'h', which is the smallest letter greater than 'f'. Similarly, for target 'n', it wraps around and returns 'd'.

My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:

Build REST APIs with Spring Boot 4, Spring Security 7, and JWT

🆕 High-Demand 80–90% OFF

[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25

🆕 High-Demand 80–90% OFF

ChatGPT + Generative AI + Prompt Engineering for Beginners

🚀 Trending Now 80–90% OFF

Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Real-Time REST APIs with Spring Boot - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Building Microservices with Spring Boot and Spring Cloud

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Java Full-Stack Developer Course with Spring Boot and React JS

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Build 5 Spring Boot Projects with Java: Line-by-Line Coding

🌟 Top Rated 80–90% OFF

Testing Spring Boot Application with JUnit and Mockito

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot Thymeleaf Real-Time Web Application - Blog App

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Master Spring Data JPA with Hibernate

🔥 Bestseller 80–90% OFF
Available in Udemy for Business

Spring Boot + Apache Kafka Course - The Practical Guide

🎓 Student Favorite 80–90% OFF
Available in Udemy for Business

Java Testing: Mastering JUnit 5 Framework

🆕 New 80–90% OFF

Reactive Programming in Java: Spring WebFlux and Testing

🌟 Top Rated 80–90% OFF

Spring Boot + RabbitMQ Course - The Practical Guide

🌟 Top Rated 80–90% OFF
Available in Udemy for Business

Functional Programming in Java (Includes Java Collections)

🎓 Student Favorite 80–90% OFF

ChatGPT for Java Developers: Boost Your Productivity with AI

🚀 Trending Now 80–90% OFF