🎓 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
This blog post discusses a sliding window problem often encountered in array processing: finding the longest subarray containing only 1’s in a binary array, given that up to K values can be changed from 0 to 1.
Problem
Given an array A of 0's and 1's, and an integer K indicating the maximum number of 0's that can be flipped to 1's, find the length of the longest contiguous subarray that contains only 1’s after at most K replacements.
Example 1:
Input: A = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
Output: 6
Explanation: Flip the 0s at index 5 and 10 to 1s to get the longest subarray.
Example 2:
Input: A = [0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1], K = 3
Output: 9
Explanation: Replace the 0s at index 6, 9, and 10 with 1s.
2. Solution Steps
1. Use the sliding window technique to process the array.
2. Keep track of the number of zeros within the current window.
3. If the number of zeros exceeds K, shrink the window from the left until it contains K or fewer zeros.
4. Update the maximum length of the window as the window changes.
5. Return the maximum length found.
3. Code Program
public class Solution {
// Main method for testing
public static void main(String[] args) {
int[] A1 = {1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0};
System.out.println("Longest subarray with ones after replacement: " + findMaxConsecutiveOnes(A1, 2));
int[] A2 = {0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1};
System.out.println("Longest subarray with ones after replacement: " + findMaxConsecutiveOnes(A2, 3));
}
// Method to find the longest subarray with ones after replacement
public static int findMaxConsecutiveOnes(int[] A, int K) {
int windowStart = 0, maxLength = 0, maxOnesCount = 0;
for (int windowEnd = 0; windowEnd < A.length; windowEnd++) {
if (A[windowEnd] == 1) {
maxOnesCount++;
}
// If the number of zeros exceeds K, shrink the window
if (windowEnd - windowStart + 1 - maxOnesCount > K) {
if (A[windowStart] == 1) {
maxOnesCount--;
}
windowStart++;
}
maxLength = Math.max(maxLength, windowEnd - windowStart + 1);
}
return maxLength;
}
}
Output:
Longest subarray with ones after replacement: 6 Longest subarray with ones after replacement: 9
Explanation:
The findMaxConsecutiveOnes method applies the sliding window technique to find the longest subarray with ones after at most K replacements. It maintains a count of the number of 1's in the window and adjusts the window size when the number of 0's exceeds K.
For example, in the array [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0] with K = 2, the longest subarray with ones after replacement is of length 6.
The method correctly identifies and counts the length of the longest subarray fulfilling the criteria.
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
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment