sourabh2k15 sourabh2k15

🎯

Focusing

SWE @ Google Brain, hacking away at JAX

sourabh2k15 / LongestSubstringWithoutRepeatingChars.cpp

Created January 8, 2018 23:10

Leetcode 3. Longest Substring Without Repeating Characters

	class Solution {
	public:
	int lengthOfLongestSubstring(string s) {
	unordered_map<char, int> seen;

	int begin = 0, end = 0;
	int len = 0;

	string ans = "";

sourabh2k15 / 76-Minimum_Window_Substring.cpp

Last active March 20, 2022 16:27

Leetcode 76. Minimum Window Substring

	class Solution {
	public:
	string minWindow(string s, string t) {
	unordered_map<char, int> table;

	// initialize frequency table for t
	for(char c : t){
	table[c]++;
	}

sourabh2k15 / levelOrder.py

Created January 6, 2018 23:23

Shad Khan's suggestion to eliminate dummy node in level order traversal code using size of queue.

	from collections import deque

	class Solution(object):
	def levelOrder(self, root):
	q = deque()

	if(root != None):
	q.append(root)

	levels = []

sourabh2k15 / 01matrix.cpp

Created January 6, 2018 21:01

542. 01 Matrix

	class Solution {
	public:
	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
	queue<vector<int>> bfs;
	int dist = 0;
	int m = matrix.size(), n = matrix[0].size();

	for(int i = 0; i < matrix.size(); i++){
	for(int j = 0; j < matrix[i].size(); j++){
	if(matrix[i][j] == 0) bfs.push(vector<int>({i, j})); // keep track of all 0's

sourabh2k15 / levelOrder2.cpp

Last active January 6, 2018 19:51

102. Binary Tree Level Order Traversal Solution using 2 queues

	class Solution {
	public:
	vector<vector<int>> levelOrder(TreeNode* root) {
	queue<TreeNode*> even;
	queue<TreeNode*> odd;
	vector<vector<int>> result;

	even.push(root);

	while(!even.empty() \|\| !odd.empty()){

sourabh2k15 / levelOrder.cpp

Last active January 6, 2018 19:51

102. Binary Tree Level Order Traversal Solution using marker

	class Solution {
	public:
	vector<vector<int>> levelOrder(TreeNode* root) {
	vector<vector<int>> result; // array of arrays to store final result
	vector<int> levelresult; // array storing result for each level temporarily

	queue<TreeNode*> bfs; // bfs queue
	TreeNode* marker = new TreeNode(INT_MIN); // dummy node to mark end of level

	bfs.push(root);

sourabh2k15 / treebfs.cpp

Created January 6, 2018 05:11

	void levelOrder(TreeNode* root) {
	queue<TreeNode*> bfs;
	bfs.push(root);

	while(!bfs.empty()){
	TreeNode* current = bfs.front(); bfs.pop();

	if(current){
	cout << current->val << " ";

sourabh2k15 / countComponents.cpp

Last active January 5, 2020 22:34

Leetcode 323. Number of Connected Components in an Undirected Graph

	class Solution {
	public:
	int countComponents(int n, vector<pair<int, int>>& edges) {
	vector<bool> visited(n, false);
	vector<vector<int>> adjList(n, vector<int>(0));
	stack<int> dfs;

	int count = 0;
	int ans = 0;

sourabh2k15 / numIslands.cpp

Created January 4, 2018 08:49

Leetcode 200. Number of Islands | connected components using recursive DFS and destruction of matrix

	class Solution {
	public:
	int numIslands(vector<vector<char>>& grid) {
	int ans = 0; // number of groups

	// iterating through given grid to find a '1'
	for(int i = 0; i < grid.size(); i++){
	for(int j = 0; j < grid[0].size(); j++){
	if(grid[i][j] == '1'){
	ans++; // start a group and visit all members of this group using dfs

sourabh2k15 / preorder.cpp

Last active June 14, 2021 05:37

Leetcode 144. Binary Tree Preorder Traversal. Using stack to perform DFS

	class Solution {
	public:
	// DFS magic : initialize stack and do the following
	// pop top, retrieve neighbours for top, push unvisited neighbours to stack \| repeat while stack not empty
	// because this is a tree no need to keep track of visited as no cycles possible.

	vector<int> preorderTraversal(TreeNode* root) {
	stack<TreeNode*> s;
	vector<int> result;