Skip to content

Instantly share code, notes, and snippets.

Viktor Karpov vitkarpov

Block or report user

Report or block vitkarpov

Hide content and notifications from this user.

Learn more about blocking users

Contact Support about this user’s behavior.

Learn more about reporting abuse

Report abuse
View GitHub Profile
@vitkarpov
vitkarpov / trapping-rain-water.cpp
Created Nov 6, 2019
Trapping Rain Water (Dynamic Programming)
View trapping-rain-water.cpp
class Solution {
public:
int trap(const vector<int>& h) {
int n = h.size();
vector<int> left_max(n + 1);
vector<int> right_max(n + 1);
for (int i = 1; i <= n; i++) {
left_max[i] = max(left_max[i - 1], h[i - 1]);
}
@vitkarpov
vitkarpov / trapping-water.cpp
Created Oct 29, 2019
42. Trapping Rain Water
View trapping-water.cpp
class Solution {
public:
int trap(const vector<int>& h) {
int n = h.size();
vector<int> left_max(n + 1);
vector<int> right_max(n + 1);
for (int i = 1; i <= n; i++) {
left_max[i] = max(left_max[i - 1], h[i - 1]);
}
View largest-rectangle-in-histogram.js
// Time: O(n * log (n))
// Memory: O(log (n))
/**
* @param {number[]} heights
* @return {number}
*/
var largestRectangleArea = function(heights) {
if (!heights.length) {
return 0;
@vitkarpov
vitkarpov / valid-parenthesis-string.js
Last active Oct 20, 2019
678. Valid Parenthesis String (dynamic programming)
View valid-parenthesis-string.js
/**
* @param {string} s
* @return {boolean}
*/
var checkValidString = function(s) {
const n = s.length;
const dp = new Array(n).fill(0).map(() => new Array(n).fill(false));
for (let i = 0; i < n; i++) {
if (s[i] == "*") {
View lru.cpp
class LRUCache {
typedef pair<int, int> Node;
typedef list<Node>::iterator ref;
list<Node> q;
unordered_map<int, ref> m;
int capacity;
void insert(int key, int value) {
if (m.find(key) != m.end()) {
View sort-colors.cpp
class Solution {
public:
void sortColors(vector<int>& nums) {
int p0 = 0;
int p1 = 0;
int p2 = nums.size() - 1;
while (p1 <= p2) {
if (nums[p1] == 1) {
p1++;
View number-of-islands.cpp
class Solution {
private:
void eraseIsland(vector<vector<char>>& grid, int x, int y) {
if (grid[y][x] == '0') {
return;
}
grid[y][x] = '0';
if (y > 0) eraseIsland(grid, x, y - 1);
if (y < grid.size() - 1) eraseIsland(grid, x, y + 1);
@vitkarpov
vitkarpov / divide-two-integers.js
Created Oct 3, 2019
Divide Two Integers (32 bits environment only, O(log n) time complexity)
View divide-two-integers.js
/**
* @param {number} dividend
* @param {number} divisor
* @return {number}
*/
var divide = function(dividend, divisor) {
if (dividend == INT_MIN && divisor == -1) {
return INT_MAX;
}
View two-sum.cpp
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int, int>> numsNpos;
for (auto i = 0; i < nums.size(); i++) {
numsNpos.push_back({ nums[i], i });
}
sort(numsNpos.begin(), numsNpos.end());
@vitkarpov
vitkarpov / Computer-Science-Club-27-12-2018.md
Last active Dec 27, 2018
Computer Science Club, 27.12.2018 (Strings)
View Computer-Science-Club-27-12-2018.md

Computer Science Club, 27.12.2018

Here's a set of problems for the class. Exploiring strings.

Is Unique

Implement an algorithm to determine if a string has all unique characters. What if you cannot use additional data structures?

Hints:

You can’t perform that action at this time.