11 months ago

Geetika Aggarwal • 20

More ones

class Solution{
public:
  // Function to count the number of substrings
  long long countSubstring(string S){
    int n=S.size();
    long long ans=0,zero=n,minus=0;
    int mp[2*n+5];
    memset(mp,0,sizeof(mp));
    int cur=zero;

    // Loop through the string to determine the number of zeros and minuses
    for(auto i:S){
      if(i=='0')
        cur--;
      else
        cur++;
      if(cur<=zero){
        minus++;
      }
      mp[cur]++;
    }
    
    // Loop through the string again to count the number of valid substrings
    for(int i=0;i<n;i++){
      ans+=(n-i-minus);
      if(S[i]=='1'){
        mp[zero+1]--;
        zero++;
        minus+=mp[zero];
      }
      else{
        mp[zero-1]--;
        zero--;
        minus--;
        minus-=mp[zero+1];
      }
    }
    return ans;
  }
};

12 months ago

JoJo • 10

Minimum Cost Path 

class Solution {
    public int minCostPath(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                max = Math.max(max, grid[i][j]);
                min = Math.min(min, grid[i][j]);
            }
        }

        int low = 0;
        int high = max - min;

        int ans = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (isPossible(grid, mid)) {
                ans = mid;
                high = mid - 1;
            } else low = mid + 1;
        }

        return ans;
    }

    private boolean isPossible(int[][] grid, int mid) {
        Deque<Pair> queue = new ArrayDeque<>();
        for (int i = 0; i < grid.length; i++) {
            queue.add(new Pair(0, grid[i][0], grid[i][0]));
        }

        while (!queue.isEmpty()) {
            Pair pair = queue.poll();
            int j = pair.j;
            if (j == grid[0].length - 1) return true;

            int next = j + 1;

            for (int i = 0; i < grid.length; i++) {
                int val = grid[i][next];
                if (Math.abs(val - pair.max) <= mid && Math.abs(val - pair.min) <= mid) {
                    queue.add(new Pair(next, Math.max(val, pair.max), Math.min(val, pair.min)));
                }
            }
        }

        return false;
    }
}

class Pair {
    int j;
    int max;
    int min;
    Pair (int j, int m, int n) {
        this.j = j;
        this.max = m;
        this.min = n;
    }
}

2 days ago

Shivam Bhadani • 10

Bengaluru

Minimum Cost Path

/* जय श्री गणेश */

#include<bits/stdc++.h>
using namespace std;

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define all(x) x.begin(), x.end()
#define nline '\n'

void run_case()
{
	int n, m;
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (auto& v : a) {
		for (auto& x : v) {
			cin >> x;
		}
	}
	vector<pair<int, int>> track;
	for (int j = 0; j < m; j++) {
		for (int i = 0; i < n; i++) {
			track.push_back({a[i][j], j});
		}
	}
	sort(all(track));
	map<int, int> mp;
	int ans = INT_MAX;
	int i = 0;
	for (int j = 0; j < n * m; j++) {
		++mp[track[j].second];
		if (mp.size() >= m) {
			while (mp[track[i].second] > 1) {
				--mp[track[i].second];
				++i;
			}
			ans = min(ans, track[j].first - track[i].first);
		}
	}
	cout << ans << nline;
}

int32_t main() {
	IOS
	int test_cases;
	cin >> test_cases;
	while (test_cases--)
	{
		run_case();
	}
	return 0;
}