8000 P-744-Find-Smallest-Letter-Greater-Than-Target · aditya-2k23/Leetcode@ceaaf7c · GitHub
[go: up one dir, main page]
Skip to content

Commit ceaaf7c

Browse files
aditya-2k23aditya-2k23
committed
P-744-Find-Smallest-Letter-Greater-Than-Target
Implements a binary search-based approach to solve LeetCode Problem 744: Find Smallest Letter Greater Than Target. Includes: - Detailed algorithm explanation in README. - C++ solution with time complexity of O(log n) and space complexity of O(1). - Comprehensive test cases to verify functionality. Enhances problem-solving efficiency and ensures correctness through rigorous testing.
1 parent 022a793 commit ceaaf7c

File tree

4 files changed

+182
-1
lines changed

4 files changed

+182
-1
lines changed

‎README.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,7 @@
22

33
[![GitHub](https://img.shields.io/badge/Repository-blue?logo=github)](https://github.com/aditya-2k23/leetcode)
44
[![License](https://img.shields.io/badge/LICENSE-MIT-yellow?logo=license.svg)](https://github.com/aditya-2k23/leetcode/blob/main/LICENSE)
5-
![Problems Solved](https://img.shields.io/badge/Solved-12-brightgreen) <!-- Update this count as you solve more problems -->
5+
![Problems Solved](https://img.shields.io/badge/Solved-13-brightgreen) <!-- Update this count as you solve more problems -->
66
![Language](https://img.shields.io/badge/Language-Python%20%7C%20Java%20%7C%20C++-orange)
77
[![Wiki](https://img.shields.io/badge/Wiki-Available-blueviolet)](https://github.com/aditya-2k23/leetcode/wiki)
88
[![Discussions](https://img.shields.io/badge/Discussions-Open-blue)](https://github.com/aditya-2k23/leetcode/discussions)
@@ -31,6 +31,7 @@ Below is a list of problems solved in this repository:
31 8000 31
- [Problem 35: Search Insert Position](problems/P-35-search-insert-position)
3232
- [Problem 88: Merge Sorted Array](problems/P-88-merge-sorted-array)
3333
- [Problem 704: Binary Search](problems/P-704-binary-search)
34+
- [Problem 744: Find Smallest Letter Greater Than Target](problems/P-744-find-smallest-letter-greater-than-target)
3435
- _(Add more problems as they are solved)_
3536

3637
## Purpose

‎problems/P-744-find-smallest-letter-greater-than-target/README.md

Lines changed: 82 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,82 @@
1+
# Problem 744: Find Smallest Letter Greater Than Target
2+
3+
- **Difficulty**: Easy
4+
- **Topics**: Array, Binary Search
5+
- **LeetCode Link**: [Problem URL](https://leetcode.com/problems/find-smallest-letter-greater-than-target/)
6+
7+
## Problem Description
8+
9+
You are given an array of characters `letters` that is sorted in **non-decreasing order**, and a character `target`. There are **at least two different** characters in `letters`.
10+
11+
Return the smallest character in `letters` that is lexicographically greater than `target`. If such a character does not exist, return the first character in `letters`.
12+
13+
**Example 1:**
14+
15+
> **Input:** letters = ["c","f","j"], target = "a"
16+
> **Output:** "c"
17+
> **Explanation:** The smallest character that is lexicographically greater than 'a' in letters is 'c'.
18+
19+
**Example 2:**
20+
21+
> **Input:** letters = ["c","f","j"], target = "c"
22+
> **Output:** "f"
23+
> **Explanation:** The smallest character that is lexicographically greater than 'c' in letters is 'f'.
24+
25+
**Example 3:**
26+
27+
> **Input:** letters = ["x","x","y","y"], target = "z"
28+
> **Output:** "x"
29+
> **Explanation:** There are no characters in letters that is lexicographically greater than 'z' so we return letters[0].
30+
31+
**Constraints:**
32+
33+
- `2 <= letters.length <= 10⁴`
34+
- `letters[i]` is a lowercase English letter.
35+
- `letters` is sorted in **non-decreasing** order.
36+
- `letters` contains at least two different characters.
37+
- `target` is a lowercase English letter.
38+
39+
## Approach
40+
41+
To solve the problem of finding the smallest letter greater than a given target in a sorted array of characters, we can utilize a binary search approach. This is efficient due to the sorted nature of the input array, allowing us to quickly narrow down the search space.
42+
43+
### Steps
44+
45+
1. Initialize two pointers, `low` and `high`, to represent the current search range within the `letters` array.
46+
2. While `low` is less than or equal to `high`, calculate the middle index `mid`.
47+
3. If the character at `mid` is less than or equal to the `target`, move the `low` pointer to `mid + 1` to search in the right half.
48+
4. If the character at `mid` is greater than the `target`, move the `high` pointer to `mid - 1` to search in the left half.
49+
5. After the loop, the `low` pointer will be positioned at the smallest character greater than the `target`, or at the end of the array if no such character exists.
50+
6. Return the character at the `low` pointer, wrapping around to the start of the array if necessary.
51+
52+
## Solution
53+
54+
- **Language**: C++
55+
- **File**: [solution.cpp](solution.cpp)
56+
57+
## Notes
58+
59+
- Ensure that the input `letters` is sorted in non-decreasing order.
60+
61+
### Complexity Analysis
62+
63+
- **Time Complexity**: `O(log n)`
64+
- The binary search reduces the search space by half with each iteration, leading to logarithmic time complexity.
65+
- **Space Complexity**: `O(1)`
66+
- The algorithm uses a constant amount of space for the pointers and does not require any additional data structures.
67+
68+
## Test Cases
69+
70+
See the [`tests`](./tests/) directory for various test cases.
71+
72+
### Running Tests
73+
74+
- **C++ (Simple)**: `cd tests; g++ test.cpp ../solution.cpp -o test; ./test`
75+
- **Python**: `cd tests; python test.py`
76+
- **Java**: `javac .\solution.java tests/test.java; java -cp ".;tests" test`
77+
78+
---
79+
80+
> **Solved on**: 06/06/2025 |
81+
> **Time taken**: 00:06:14 |
82+
> **Attempts**: 2

‎problems/P-744-find-smallest-letter-greater-than-target/solution.cpp

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
/*
2+
* LeetCode Problem: 744. Find Smallest Letter Greater Than Target
3+
* Difficulty: Easy
4+
* Topics: Array, Binary Search
5+
* Date Solved: 06/06/2025
6+
*/
7+
8+
#include <bits/stdc++.h>
9+
using namespace std;
10+
11+
class Solution {
12+
public:
13+
char nextGreatestLetter(vector<char>& letters, char target) {
14+
int low = 0, high = letters.size() - 1;
15+
16+
while (low <= high) {
17+
int mid = low + (high - low) / 2;
18+
19+
if (letters[mid] <= target)
20+
low = mid + 1;
21+
else
22+
high = mid - 1;
23+
}
24+
25+
return letters[low % letters.size()];
26+
}
27+
};

‎problems/P-744-find-smallest-letter-greater-than-target/tests/test.cpp

Lines changed: 71 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,71 @@
1+
#include "../solution.cpp"
2+
#include <bits/stdc++.h>
3+
using namespace std;
4+
5+
// Helper to print char result
6+
void printResult(const char& result) {
7+
cout << "'" << result << "'";
8+
}
9+
10+
// Helper to print vector<char>
11+
void printVector(const vector<char>& vec) {
12+
cout << "[";
13+
for (size_t i = 0; i < vec.size(); ++i) {
14+
cout << "'" << vec[i] << "'";
15+
if (i < vec.size() - 1) cout << ",";
16+
}
17+
cout << "]";
18+
}
19+
20+
// Test function for Solution::nextGreatestLetter
21+
bool testFunction(const vector<char>& input1, char input2, char expected, int testNumber) {
22+
Solution sol;
23+
vector<char> letters = input1;
24+
char result = sol.nextGreatestLetter(letters, input2);
25+
26+
cout << "Test Case " << testNumber << ": ";
27+
cout << "Input1: ";
28+
printVector(input1);
29+
cout << " Input2: '" << input2 << "' ";
30+
if (result == expected) {
31+
cout << "\tOutput: ";
32+
printResult(result);
33+
cout << "\t";
34+
cout << "Expected: ";
35+
printResult(expected);
36+
cout << " Passed\n";
37+
return true;
38+
}
39+
else {
40+
cout << "Failed: Expected ";
41+
printResult(expected);
42+
cout << ", Got ";
43+
printResult(result);
44+
cout << "\n";
45+
return false;
46+
}
47+
}
48+
49+
void runTests() {
50+
int passed = 0, total = 0;
51+
52+
// Test cases for LeetCode 744
53+
if (testFunction({ 'c','f','j' }, 'a', 'c', ++total)) passed++;
54+
if (testFunction({ 'c','f','j' }, 'c', 'f', ++total)) passed++;
55+
if (testFunction({ 'c','f','j' }, 'd', 'f', ++total)) passed++;
56+
if (testFunction({ 'c','f','j' }, 'g', 'j', ++total)) passed++;
57+
if (testFunction({ 'c','f','j' }, 'j', 'c', ++total)) passed++;
58+
if (testFunction({ 'c','f','j' }, 'k', 'c', ++total)) passed++;
59+
if (testFunction({ 'a','b' }, 'z', 'a', ++total)) passed++;
60+
if (testFunction({ 'a','b' }, 'a', 'b', ++total)) passed++;
61+
if (testFunction({ 'a','b' }, 'b', 'a', ++total)) passed++;
62+
63+
cout << "\nTest Results: " << passed << "/" << total << " passed.\n";
64+
if (passed == total) cout << "All tests passed!\n";
65+
else cout << "Some tests failed.\n";
66+
}
67+
68+
int main() {
69+
runTests();
70+
return 0;
71+
}

0 commit comments

Comments
 (0)
0