Posts tagged as “brute force”

花花酱 LeetCode 1534. Count Good Triplets

By zxi on August 1, 2020

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

0 <= i < j < k < arr.length
|arr[i] - arr[j]| <= a
|arr[j] - arr[k]| <= b
|arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

Constraints:

3 <= arr.length <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

Solution: Brute Force

Time complexity: O(n^3)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int countGoodTriplets(vector<int>& arr, int a, int b, int c) {

const int n = arr.size();

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

for (int k = j + 1; k < n; ++k)

if (abs(arr[i] - arr[j]) <= a &&

abs(arr[j] - arr[k]) <= b &&

abs(arr[i] - arr[k]) <= c)

++ans;

return ans;

}

};

花花酱 LeetCode 1450. Number of Students Doing Homework at a Given Time

By zxi on May 16, 2020

Given two integer arrays startTime and endTime and given an integer queryTime.

The ith student started doing their homework at the time startTime[i] and finished it at time endTime[i].

Return the number of students doing their homework at time queryTime. More formally, return the number of students where queryTime lays in the interval [startTime[i], endTime[i]] inclusive.

Example 1:

Input: startTime = [1,2,3], endTime = [3,2,7], queryTime = 4
Output: 1
Explanation: We have 3 students where:
The first student started doing homework at time 1 and finished at time 3 and wasn't doing anything at time 4.
The second student started doing homework at time 2 and finished at time 2 and also wasn't doing anything at time 4.
The third student started doing homework at time 3 and finished at time 7 and was the only student doing homework at time 4.

Example 2:

Input: startTime = [4], endTime = [4], queryTime = 4
Output: 1
Explanation: The only student was doing their homework at the queryTime.

Example 3:

Input: startTime = [4], endTime = [4], queryTime = 5
Output: 0

Example 4:

Input: startTime = [1,1,1,1], endTime = [1,3,2,4], queryTime = 7
Output: 0

Example 5:

Input: startTime = [9,8,7,6,5,4,3,2,1], endTime = [10,10,10,10,10,10,10,10,10], queryTime = 5
Output: 5

Constraints:

startTime.length == endTime.length
1 <= startTime.length <= 100
1 <= startTime[i] <= endTime[i] <= 1000
1 <= queryTime <= 1000

Solution: Brute Force

Time complexity: O(n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int busyStudent(vector<int>& startTime, vector<int>& endTime, int queryTime) {

int ans = 0;

for (int i = 0; i < startTime.size(); ++i)

if (startTime[i] <= queryTime && queryTime <= endTime[i]) ++ans;

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def busyStudent(self, startTime: List[int], endTime: List[int], queryTime: int) -> int:

return sum(s <= queryTime <= e for s, e in zip(startTime, endTime))

花花酱 LeetCode 1385. Find the Distance Value Between Two Arrays

By zxi on March 21, 2020

Given two integer arrays arr1 and arr2, and the integer d, return the distance value between the two arrays.

The distance value is defined as the number of elements arr1[i] such that there is not any element arr2[j] where |arr1[i]-arr2[j]| <= d.

Example 1:

Input: arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
Output: 2
Explanation: 
For arr1[0]=4 we have: 
|4-10|=6 > d=2 
|4-9|=5 > d=2 
|4-1|=3 > d=2 
|4-8|=4 > d=2 
For arr1[1]=5 we have: 
|5-10|=5 > d=2 
|5-9|=4 > d=2 
|5-1|=4 > d=2 
|5-8|=3 > d=2
For arr1[2]=8 we have:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2

Example 2:

Input: arr1 = [1,4,2,3], arr2 = [-4,-3,6,10,20,30], d = 3
Output: 2

Example 3:

Input: arr1 = [2,1,100,3], arr2 = [-5,-2,10,-3,7], d = 6
Output: 1

Constraints:

1 <= arr1.length, arr2.length <= 500
-10^3 <= arr1[i], arr2[j] <= 10^3
0 <= d <= 100

Solution 1: All pairs

Time complexity: O(m*n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

int ans = 0;

for (int x : arr1) {

bool flag = true;

for (int y : arr2)

if (abs(x - y) <= d) {

flag = false;

break;

}

ans += flag;

}

return ans;

}

};

Python3

# Author: Huahua

class Solution:

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:

return sum(all(abs(x - y) > d for y in arr2) for x in arr1)

Solution 2: Two Pointers

Sort arr1 in ascending order and sort arr2 in descending order.
Time complexity: O(mlogm + nlogn + m + n)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

sort(begin(arr1), end(arr1));

sort(rbegin(arr2), rend(arr2));

int ans = 0;

for (int a : arr1) {

while (arr2.size() && arr2.back() < a - d)

arr2.pop_back();

ans += arr2.empty() || arr2.back() > a + d;

}

return ans;

}

};

Solution 3: Binary Search

Sort arr2 in ascending order. and do two binary searches for each element to determine the range of [a-d, a+d], if that range is empty we increase the counter

Time complexity: O(mlogm + nlogm)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

int findTheDistanceValue(vector<int>& arr1, vector<int>& arr2, int d) {

sort(begin(arr2), end(arr2));

int ans = 0;

for (int a : arr1) {

auto it1 = lower_bound(begin(arr2), end(arr2), a - d);

auto it2 = upper_bound(begin(arr2), end(arr2), a + d);

if (it1 == it2) ++ans;

}

return ans;

}

};

花花酱 LeetCode 1237. Find Positive Integer Solution for a Given Equation

By zxi on October 27, 2019

Given a function f(x, y) and a value z, return all positive integer pairs x and y where f(x,y) == z.

The function is constantly increasing, i.e.:

f(x, y) < f(x + 1, y)
f(x, y) < f(x, y + 1)

The function interface is defined like this:

interface CustomFunction {
public:
  // Returns positive integer f(x, y) for any given positive integer x and y.
  int f(int x, int y);
};

For custom testing purposes you’re given an integer function_id and a target z as input, where function_id represent one function from an secret internal list, on the examples you’ll know only two functions from the list.

You may return the solutions in any order.

Example 1:

Input: function_id = 1, z = 5
Output: [[1,4],[2,3],[3,2],[4,1]]
Explanation: function_id = 1 means that f(x, y) = x + y

Example 2:

Input: function_id = 2, z = 5
Output: [[1,5],[5,1]]
Explanation: function_id = 2 means that f(x, y) = x * y

Constraints:

1 <= function_id <= 9
1 <= z <= 100
It’s guaranteed that the solutions of f(x, y) == z will be on the range 1 <= x, y <= 1000
It’s also guaranteed that f(x, y) will fit in 32 bit signed integer if 1 <= x, y <= 1000

Solution1 : Brute Force

Time complexity: O(1000*1000)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> findSolution(CustomFunction& customfunction, int z) {

vector<vector<int>> ans;

for (int x = 1; x <= 1000; ++x) {

if (customfunction.f(x, 1) > z) break;

for (int y = 1; y <= 1000; ++y) {

int t = customfunction.f(x, y);

if (t > z) break;

if (t == z) ans.push_back({x, y});

}

return ans;

}

};

花花酱 LeetCode 681. Next Closest Time

By zxi on September 24, 2017

Problem:

https://leetcode.com/problems/next-closest-time/description/
no limit on how many times a digit can be reused.

You may assume the given input string is always valid. For example, “01:34”, “12:09” are all valid. “1:34”, “12:9” are all invalid.

Example 1:

Input: "19:34"
Output: "19:39"
Explanation: The next closest time choosing from digits 1, 9, 3, 4, is 19:39, 
which occurs 5 minutes later.  
It is not 19:33, because this occurs 23 hours and 59 minutes later.

Example 2:

Input: "23:59"
Output: "22:22"
Explanation: The next closest time choosing from digits 2, 3, 5, 9, is 22:22. 
It may be assumed that the returned time is next day's time since it is smaller 
than the input time numerically.

Ads

Solution1: Brute force

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

set<char> s(time.begin(), time.end());

int hour = stoi(time.substr(0, 2));

int min = stoi(time.substr(3, 2));

while (true) {

if (++min == 60) {

min = 0;

(++hour) %= 24;

}

char buffer[5];

sprintf(buffer, "%02d:%02d", hour, min);

set<char> s2(buffer, buffer + sizeof(buffer));

if (includes(s.begin(), s.end(), s2.begin(), s2.end()))

return string(buffer);

}

return time;

}

};

Java

// Author: Huahua

// Running time: 85 ms

class Solution {

public String nextClosestTime(String time) {

int hour = Integer.parseInt(time.substring(0, 2));

int min = Integer.parseInt(time.substring(3, 5));

while (true) {

if (++min == 60) {

min = 0;

++hour;

hour %= 24;

}

String curr = String.format("%02d:%02d", hour, min);

Boolean valid = true;

for (int i = 0; i < curr.length(); ++i)

if (time.indexOf(curr.charAt(i)) < 0) {

valid = false;

break;

}

if (valid) return curr;

}

Python

"""

Author: Huahua

Running time: 65 ms

"""

class Solution:

def nextClosestTime(self, time):

s = set(time)

hour = int(time[0:2])

minute = int(time[3:5])

while True:

minute += 1

if minute == 60:

minute = 0

hour = 0 if hour == 23 else hour + 1

time = "%02d:%02d" % (hour, minute)

if set(time) <= s:

return time

Solution 2: DFS

C++

// Author: Huahua

// Running time: 3 ms

class Solution {

public:

string nextClosestTime(string time) {

vector<int> d = {

time[0] - '0', time[1] - '0', time[3] - '0', time[4] - '0' };

int h = d[0] * 10 + d[1];

int m = d[2] * 10 + d[3];

vector<int> curr(4, 0);

int now = toTime(h, m);

int best = now;

dfs(0, d, curr, now, best);

char buff[5];

sprintf(buff, "%02d:%02d", best / 60, best % 60);

return string(buff);

}

private:

void dfs(int dep, const vector<int>& digits, vector<int>& curr, int time, int& best) {

if (dep == 4) {

int curr_h = curr[0] * 10 + curr[1];

int curr_m = curr[2] * 10 + curr[3];

if (curr_h > 23 || curr_m > 59) return;

int curr_time = toTime(curr_h, curr_m);

if (timeDiff(time, curr_time) < timeDiff(time, best))

best = curr_time;

return;

}

for (int digit : digits) {

curr[dep] = digit;

dfs(dep + 1, digits, curr, time, best);

}

int toTime(int h, int m) {

return h * 60 + m;

}

int timeDiff(int t1, int t2) {

if (t1 == t2) return INT_MAX;

return ((t2 - t1) + 24 * 60) % (24 * 60);

}

};

Solution 3: Brute force + Time library

Python3

"""

Author: Huahua

Running time: 292 ms

"""

from datetime import *

class Solution:

def nextClosestTime(self, time):

s = set(time)

while True:

time = (datetime.strptime(time, '%H:%M') +

timedelta(minutes=1)).strftime('%H:%M')

if set(time) <= s:

return time

Posts tagged as “brute force”

花花酱 LeetCode 1534. Count Good Triplets

Solution: Brute Force

C++

花花酱 LeetCode 1450. Number of Students Doing Homework at a Given Time

Solution: Brute Force

C++

Python3

花花酱 LeetCode 1385. Find the Distance Value Between Two Arrays

Solution 1: All pairs

C++

Python3

Solution 2: Two Pointers

C++

Solution 3: Binary Search

C++

花花酱 LeetCode 1237. Find Positive Integer Solution for a Given Equation

Solution1 : Brute Force

C++

花花酱 LeetCode 681. Next Closest Time

Problem:

Example 1:

Example 2:

Solution1: Brute force

C++

Java

Python

Solution 2: DFS

C++

Solution 3: Brute force + Time library

Python3

Related Problems: