The Solution to the Instagram Challenge: Longest Increasing Temperature Streak
Hey Technophiles, I Hope you are all doing well.
Sunday (01/09/2024), we posted a challenge on our Instagram page! If you didn’t check the post do visit our page, and kindly follow us on Instagram.
Instagram Post: View Post
Stay connected with us:
Problem Breakdown:
The input is a list of temperatures, and the goal is to find the longest increasing streak of temperatures. For example:
- Input:
[70, 74, 76, 75, 78, 79, 83, 77, 80] - Output:
[75, 78, 79, 83]
Here, the longest streak where each temperature is greater than the one before is from 75 to 83. Simple enough, right?
Now, let’s write some code to solve it.
The Solution in C:
// Optimized Code
#include <stdio.h>
void longest_increasing_streak(int temps[], int n) {
int max_start = 0, max_length = 0;
int current_start = 0, current_length = 1;
for (int i = 1; i < n; i++) {
if (temps[i] > temps[i - 1]) {
current_length++;
} else {
if (current_length > max_length) {
max_start = current_start;
max_length = current_length;
}
current_start = i;
current_length = 1;
}
}
// Final check
if (current_length > max_length) {
max_start = current_start;
max_length = current_length;
}
// Print the longest streak
printf("[");
for (int i = max_start; i < max_start + max_length; i++) {
printf("%d", temps[i]);
if (i < max_start + max_length - 1) {
printf(", ");
}
}
printf("]\n");
}
int main() {
int temps[] = {70, 74, 76, 75, 78, 79, 83, 77, 80};
int n = sizeof(temps) / sizeof(temps[0]);
longest_increasing_streak(temps, n);
// Output: [75, 78, 79, 83]
return 0;
}
// Time Complexity - O(n)
// Space Complexity - O(1)
How It Works:
- We use variables
max_startandmax_lengthto track the starting index and length of the longest streak, andcurrent_startandcurrent_lengthto track the current streak. - We iterate through the list of temperatures, increasing
current_lengthwhen we find a rising temperature. If the current streak ends, we check if it’s the longest so far and update accordingly. - After the loop, we do a final check to see if the longest streak is at the end.
- Finally, we print the longest increasing streak.
The Solution in Python:
// Optimized Code
def longest_increasing_streak(temps):
if not temps: # edge case: if list is empty
return []
max_streak = [] # To store the longest streak
current_streak = [temps[0]] # Start with the first temperature
# Iterate through the temperatures
for i in range(1, len(temps)):
if temps[i] > temps[i - 1]: # If the current temperature is increasing
current_streak.append(temps[i]) # Add to the current streak
else:
# Compare and update the max streak
if len(current_streak) > len(max_streak):
max_streak = current_streak
current_streak = [temps[i]] # Reset streak
# Final check after the loop
if len(current_streak) > len(max_streak):
max_streak = current_streak
return max_streak
# Example usage
temps = [70, 74, 76, 75, 78, 79, 83, 77, 80]
print(longest_increasing_streak(temps)) # Output: [75, 78, 79, 83]
// Time Complexity - O(n)
// Space Complexity - O(n)
How It Works:
- First, we handle the case where the list is empty (because we don’t want to break things).
- We initialize
max_streakto keep track of the longest increasing streak andcurrent_streakto track the current streak as we iterate through the list. - For each temperature, if it’s greater than the previous one, we add it to
current_streak. Otherwise, we compare the length ofcurrent_streakwithmax_streak, updatemax_streakif needed, and resetcurrent_streak. - Finally, after the loop, we make one last check in case the longest streak is at the end.
The Solution in Java:
// Optimized Code
import java.util.ArrayList;
import java.util.List;
public class LongestIncreasingStreak {
public static List<Integer> longestIncreasingStreak(int[] temps) {
List<Integer> maxStreak = new ArrayList<>();
List<Integer> currentStreak = new ArrayList<>();
currentStreak.add(temps[0]);
for (int i = 1; i < temps.length; i++) {
if (temps[i] > temps[i - 1]) {
currentStreak.add(temps[i]);
} else {
if (currentStreak.size() > maxStreak.size()) {
maxStreak = new ArrayList<>(currentStreak);
}
currentStreak.clear();
currentStreak.add(temps[i]);
}
}
if (currentStreak.size() > maxStreak.size()) {
maxStreak = new ArrayList<>(currentStreak);
}
return maxStreak;
}
public static void main(String[] args) {
int[] temps = {70, 74, 76, 75, 78, 79, 83, 77, 80};
System.out.println(longestIncreasingStreak(temps)); // Output: [75, 78, 79, 83]
}
}
// Time Complexity - O(n)
// Space Complexity - O(n)
How It Works:
- We use two lists:
maxStreakto hold the longest streak andcurrentStreakto track the ongoing streak. - We iterate through the array, adding to
currentStreakif the current temperature is greater than the previous one. When the streak ends, we compare it withmaxStreakand update accordingly. - After the loop, we perform a final check to see if the longest streak is at the end.
- The result is returned as a list of integers representing the longest increasing streak.
Conclusion
We’ve explored how to find the longest increasing streak in a list of temperatures using three popular programming languages. Each language has its pros and cons, but the logic behind them remains the same.
Which approach did you find the easiest to understand? Let me know in the comments if you have any suggestions or if you need further clarification!