Find k zeroes to be flipped so that number of consecutive 1’s is maximized


  • 1
    B

    Given a binary array and an integer k, find the position of zeroes flipping which creates maximum number of consecutive 1s in array.

    Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
    m = 2
    Output: 5 7
    We are allowed to flip maximum 2 zeroes. If we flip
    arr[5] and arr[7], we get 8 consecutive 1's which is
    maximum possible under given constraints

    Input: arr[] = {1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1}
    m = 1
    Output: 7

    Input: arr[] = {0, 0, 0, 1}
    m = 4
    Output: 0 1 2


  • 0
    V

    CPP solution: I think there is a better solution to this problem. The complexity of this solution is O(n^2) worst case. For every zero in an array, I am checking for both if it's modified and if it's not modified. Suggestions?

    #include "stdio.h"
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    
    class Solution{
    public:
        vector<int> findZeros(vector<int>& nums, int m){
            vector<int> res;
            if(m==0 || nums.size()==0)return res;
            findZeros(nums,m,0,res,0);
            return sol;
        }
        
    private:
        int max_ones = 0;
        vector<int> sol; // value to be returned
        void findZeros(vector<int>& nums, int m, int ones, vector<int> ret,int index){
            if(index>=nums.size()-1){
                if(ones>max_ones){
                    max_ones = ones;
                    sol = ret;
                }
                return;
            }
            while(nums[index]!=0 && index<nums.size()-1){
                index++;
                ones++;
            }
            if(m>0 && nums[index]==0){
                ret.push_back(index);
                findZeros(nums,m-1, ones, ret, index+1);
                ret.pop_back();
            }
            if(nums[index]==0)
                findZeros(nums,m,0,ret,index+1);
            else
                findZeros(nums,m,ones,ret,index+1);
            return;
        }
    }solution;
    
    int main(){
        vector<int> nums = {1,0,0,1,1,0,1,0,1,1,1};
        vector<int> ans = solution.findZeros(nums,2);
        for(int num:ans) cout << num << " " ;
        return 0;
    }
    

  • 0
    A

    you can use sliding window concept. complexity will be O(n).


  • 0
    P

    what do you think about this solution?

    #include<iostream>
    using namespace std;
    
    int main()
    {
    int max;
    int n=11;
    int arr[]={1,0,0,1,1,0,1,0,1,1,1};
    for (int j=0;j<2;j++)
    {
    int count=0;
    int sum1=0;
    max=0;
    int position;
    int final_position;
    for (int i=0;i<n;i++)
    {
    
        if (arr[i]==1){
            if (sum1==0) {
                position=i;
            }
            sum1=sum1+1;
        }
    
        if (arr[i]==0 || i==n-1)
        {
            if (sum1>max) {
                final_position=position;
                max=sum1;
            }
            sum1=0;
        }
    }
    arr[final_position-1]=1;
    cout<<final_position-1<<endl;
    }
    }
    

  • 0
    O

    As suggested above, a sliding window can give O(n) performance. The keys to note are 1) if you reach a zero and can flip it, do so because that's the only way to extend the run of consecutive ones, 2) if you reach a zero and cannot flip it, see if undoing the first flip is better or not. I did not find a way to handle (maxFlips == 0) gracefully.

    #include <deque>
    #include <vector>
    
    struct Memo
    {
        std::size_t flippedIndex;
    
        // Number of ones lost if this index is unflipped.
        std::size_t consecutiveOnes;
    
        Memo(const std::size_t flippedIndex, const std::size_t consecutiveOnes)
            : flippedIndex(flippedIndex), consecutiveOnes(consecutiveOnes)
        {
        }
    };
    
    std::size_t getFlipIndexes(const std::vector<int>& values,
        const std::size_t maxFlips, const std::size_t usedFlips,
        const std::size_t i, const std::size_t consecutiveOnes,
        std::deque<Memo>& memos, std::size_t& lastIndex)
    {
        // Avoid recursion for runs of ones.
        std::size_t j = i;
        for (; j < values.size(); ++j)
        {
            if (values[j] != 1) break;
        }
        const std::size_t onesFromI = j - i;
        if (j == values.size())
        {
            lastIndex = j;
            return consecutiveOnes + onesFromI;
        }
    
        if (maxFlips > usedFlips)
        {
            // Flip values[j] so there are a bunch of + 1 coming up.
            const std::size_t onesLost = (memos.empty())
                ? consecutiveOnes + onesFromI + 1
                : j - memos.back().flippedIndex;
            memos.push_back(Memo(j, onesLost));
            return getFlipIndexes(values, maxFlips, usedFlips + 1, j + 1,
                consecutiveOnes + onesFromI + 1, memos, lastIndex);
        }
    
        if (!memos.empty())
        {
            // Unflip the first one and recurse from j.
            const Memo removed = memos.front();
            memos.pop_front();
            const std::size_t rConsecutiveOnes = getFlipIndexes(values, maxFlips,
                usedFlips - 1, j,
                consecutiveOnes + onesFromI - removed.consecutiveOnes, memos,
                lastIndex);
            if (rConsecutiveOnes > (consecutiveOnes + onesFromI))
            {
                return rConsecutiveOnes;
            }
            // Unflipping was not better so reflip.
            memos.push_front(removed);
        }
        lastIndex = j;
        return consecutiveOnes + onesFromI;
    }
    
    std::vector<std::size_t> getFlipIndexes(const std::vector<int>& values,
        const std::size_t maxFlips, std::size_t& consecutiveOnes)
    {
        std::deque<Memo> maxMemos;
        std::size_t maxConsecutiveOnes = 0;
    
        // The while loop will only execute once as long as (maxFlips > 0).
        std::size_t lastIndex = 0;
        while (lastIndex < (values.size() - 1))
        {
            std::deque<Memo> memos;
            consecutiveOnes = getFlipIndexes(values, maxFlips, 0, lastIndex, 0, memos,
                lastIndex);
            if (consecutiveOnes > maxConsecutiveOnes)
            {
                maxConsecutiveOnes = consecutiveOnes;
                maxMemos.clear();
                maxMemos.swap(memos);
            }
    
            // Special case for (maxFlips == 0) && (values[lastIndex] == 0).
            if (0 == consecutiveOnes)
            {
                ++lastIndex;
            }
        }
    
        std::vector<std::size_t> indexes;
        for (auto memo : maxMemos)
        {
            indexes.push_back(memo.flippedIndex);
        }
        consecutiveOnes = maxConsecutiveOnes;
        return indexes;
    }
    
    void main()
    {
        const std::vector<int> input = { 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1 };
        const std::size_t maxFlips = 2;
        //const std::vector<int> input = { 0, 0, 0, 1 };
        //const std::size_t maxFlips = 1;
    
        std::size_t consecutiveOnes;
        auto indexes = getFlipIndexes(input, maxFlips, consecutiveOnes);
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.