Questions tagged [complexity]

Complexity is the analysis of how the time and space requirements of an algorithm vary according to the size of the input. Use this tag for reviews where the "Big O" is a concern.

Filter by
Sorted by
Tagged with
8
votes
6answers
12k views

Find maximum difference between values in an array

My task is to use the following pseudocode and improve it (make it run faster). Also I have to analyze the runtime of the given pseudocode and of my new code that i improved. What does this algorithm ...
4
votes
1answer
832 views

Time complexity of Max counters

As per the instructions are given in MaxCounters-Codility, You are given N counters, initially set to 0, and you have two possible operations on them: <...
1
vote
2answers
83 views

Parser for file made up of sections

I'm parsing a file made up of various sections. I have a current_section variable that tracks which portion of the file I'm currently processing and the following <...
3
votes
1answer
87 views

Substring search in Java

I am trying to make an algorithm that will find the index of a given substring (which I have labeled pattern) in a given String (...
2
votes
1answer
696 views

Return the optimal time slot

Implement a function meetingPlanner that given the availability, slotsA and slotsB, of two people and a meeting duration dur, returns the earliest time slot that works for both of them and is of ...
0
votes
0answers
50 views

Speed-up anomaly detection for pandas dataframes with vectorized operations

Motivation: I very often face a task where I need to check that dataframe's values are correct or not. Based on it I can create another dataframe with True/False values which are based on the first ...
3
votes
1answer
75 views

strstr implementation with python and sets

Please review my strstr implementation in terms of time/space efficiency and overall readability. I am preparing for a coding assessment coming up as I am looking to pivot my career from Physics to ...
3
votes
2answers
64 views

Optimize nested loops for counting the total number of selections

The question is: To select 2 numbers out of n positive integer inputs (order matters), where the number that is placed anywhere before the second must be greater than the second by a given number m. ...
0
votes
1answer
2k views

Python Implementation: Summer of 69

SUMMER OF '69: Return the sum of the numbers in the array, except ignore sections of numbers starting with a 6 and extending to the next 9 (every 6 will be followed by at least one 9). Return 0 ...
1
vote
0answers
41 views

Monotonic stack - complexity analysis

I tried following the official solution of LC975 (https://leetcode.com/problems/odd-even-jump/), using a monotonic stack - i.e., I reimplemented their solution (Approach 1) from python in C++. TLDR ...
2
votes
4answers
90 views

Is this an efficient/correct way to get largest Prime factor?

Is this an efficient way to get the largest prime factor of a given number? Other solutions I found involved nested algorithms. ...
2
votes
0answers
53 views

Sorting Algorithm using Modified Merge sort

I've been messing around with merge sort. Instead of doing a recursive division of the array I chose to keep keep track of the middle index of every three numbers. Using the index of the middle number,...
4
votes
1answer
90 views

Modelling Immerman–Szelepcsényi in Haskell

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...
3
votes
2answers
214 views

Merge arrays in objects in array based on property

I have the following code which takes an array that might have duplicate ids and will merge the items of those duplicate, and ...
4
votes
1answer
126 views

Performant Sort function for big arrays

In sort(arr), I want to sort an array. Children must be beneath their parent. And children of the same parent are sorted using ...
2
votes
2answers
178 views

LeetCode 3Sum Java Solution

I have this Java solution to LeetCode's 3Sum problem. I would be really grateful if I could get feedback on correctness, scalability, efficiency, coding best practices, and OOP design. I'm relatively ...
2
votes
0answers
52 views

2D Array Word Search: Complexity and Optimization

🧩 Objective Determine whether a given word is contained in a 2D Array word search. 🔎 Question 1. What are the time and space complexities of the current algorithm? Time complexity Linear: \$O(2(r * ...
0
votes
1answer
80 views

Generate unique string permutations recursively

🧩 Objective Write a recursive method for generating all permutations of an input string. Return them as a set. See: Recursive String Permutations - Interview Cake 🔎 Questions 1: How does the ...
1
vote
1answer
216 views

Most efficient solution for USACO: Cow Gymnastics - Python

I was trying to figure out this problem, and I did. However, my code is so abhorrently ugly that I want to tear out my eyeballs when I look at it: ...
2
votes
2answers
76 views

Cyclomatic Complexity (complexity)

I have a program for finding shortest distance/path and I got a correct answer but I am getting an issue i.e., "Function 'shortestPath' has a complexity of 9. Maximum allowed is 6." This is ...
6
votes
1answer
104 views

01 Matrix is too slow when solved using DFS

I tried solving Leetcode 01 Matrix problem. It is running too slow when solved using DFS approach. Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell. The distance ...
2
votes
1answer
66 views

Ensuring if an object is Assignable from a class type

I am trying to ensure type in the below method. How to reduce its cognitive complexity to below 15 from the current 27? It looks more readable as it is? Is there a way to break this down to make it ...
3
votes
2answers
331 views

Most Efficient Solution for USACO: Triangles - Python

I'm trying to solve this problem with Python 3.8. In my code, I used 3 nested for loops to check every single point and storing the largest area with each set of points. This program works fine, but ...
7
votes
2answers
238 views

Best Algorithm for solving USACO: Photoshoot - Python

I was trying to solve this problem with Python 3.8. I couldn't find a way other than to brute-force calculate all the possible permutations then check which permutation was valid. The program works ...
-4
votes
1answer
49 views

What is the time complexity problem I need to manage on a Hackerank “Ransom Note” - my code runs perfectly [closed]

I am trying to solve the "Ransom Note" problem on hackerank. Why isn't my code getting submitted? What can I do differently? is my total time complexity, in this case, it is O(n^2)? ...
2
votes
2answers
139 views

Dynamic Array Based Stack in C

I wrote a dynamic stack in C that uses an array as a structure. I tried to maintain O(1) for push and pop and believe I have done so. I want to know what can be written in a cleaner way and if there ...
8
votes
3answers
3k views

Counting Balanced numbers in a given array

I am trying a code challenge. Here is the problem description: When an element is deleted from an array, the higher-indexed elements shift down one index to fill the gap. A "balancing element&...
2
votes
1answer
104 views

Car Pooling algorithm time complexity

I created a solution for the car pooling algorithm. Problem: You are driving a vehicle that has capacity empty seats initially available for passengers. The vehicle only drives east (ie. it cannot ...
7
votes
2answers
126 views

Determine the complexity of sorting a binary array

The challenge is to sort an integer array containing only ones and zeros with the lowest complexity possible. As always, I am interested in any improvements suggested but in this question I am most ...
5
votes
1answer
66 views

Closest Pair heuristics, graph with adjacency matrix in C++17

I was trying to solve a problem that was briefly mentioned at the beginning of the "The Algorithm Design Manual" by Steven Skiena (Ch 1, Problem 26). It took me some time to build a working ...
23
votes
9answers
4k views

The fastest way to find one unique value when all other values are the same

I have completed this question and I am wondering what is the fastest way to solve it. The question is "There is an array with some numbers. All numbers are equal except for one. Try to find it!&...
6
votes
5answers
2k views

Sort an array of 0s, 1s and 2s in Java

Write a program to sort an array of 0's,1's and 2's in ascending order. Input: The first line contains an integer 'T' denoting the total number of test cases. In each test cases, First ...
2
votes
0answers
31 views

Benchmarking multiple implementations of a Code Kata: queue for the self-checkout tills at the supermarket

I was reading this question: Why is my function timing out when run with a larger data set? And although I couldn't quite grasp the OP's implementation and so didn't feel like answering. I did some ...
6
votes
4answers
1k views

Computing the item price and vat for a given pricing, order, and exchange rate

How can I improve the readability of the below function using a list comprehension? Also, is there a way to improve items() performance? ...
2
votes
1answer
32 views

Improving time complexity for Count the Islands DFS

For game AI development, I am currently using a slight modification on the DFS "count the islands" problem (specification below) as a solution to the ...
1
vote
1answer
55 views

Faster binary search to find the index in Python?

I am implementing a binary search algorithm and my code is as shown bellow: ...
1
vote
1answer
44 views

Link downloaded subtitle files and video files

This code unzips the downloaded subtitle files and maps them to their corresponding video file. Currently, after pairing video files with their corresponding subtitle files, it links them by renaming ...
7
votes
2answers
2k views

Simplify function to sum the absolute value of the difference between all pairs of elements of a sorted array

Given a sorted array of N elements, I need to find the absolute sum of the differences of all elements. Given 4 elements (1, 2, 3 and 4): |1-2|+|1-3|+|1-4|+|2-3|+|2-4|+|3-4| = 10 Here is my code ...
7
votes
2answers
1k views

Google's Python exercise about lists very different from the given solution

I found some Python exercises that were made by Google in their Python classes and decided to spend some time with them. Given the following description: E. Given two lists sorted in increasing order,...
2
votes
1answer
33 views

Time and Space Complexity of Leetcode Problem #31. Next Permutation

The question is as follows: Given a collection of distinct integers, return all possible permutations. Example: ...
4
votes
2answers
546 views

Time and Space Complexity of Prime factorization

I have written a function that prints all the prime factors for a given number. Here is my code ...
5
votes
4answers
292 views

LeetCode: Roman to Integer in Java

I tried solve this easy leetcode challenge in java. Challenge link Here is my solution ...
4
votes
6answers
2k views

Award Budget Cuts implementation in Java

PRAMP Award Budget Cuts The awards committee of your alma mater (i.e. your college/university) asked for your assistance with a budget allocation problem they’re facing. Originally, the committee ...
1
vote
3answers
126 views

Refactor Java code

I was trying to solve the following question: You are given 2 arrays: one representing the time people arrive at a door and other representing the direction they want to go(in or out) You have to ...
2
votes
1answer
33 views

What is the optimal way to retrieve a list of sorted dates in a list of sorted periods in python?

Suppose I have a list with N sorted dates and M non-overlapping sorted periods with start date, end date (inclusive), and a tax rate for example. I have to make an efficient algorithm retrieve all tax ...
1
vote
0answers
34 views
2
votes
1answer
116 views

Finding the closest pair of numbers which add to a target number

This function takes two lists of same length and a target number: the number which is to be summed. The function then returns a list of pairs whose sum is closest to the target number than any other ...
0
votes
2answers
73 views

Python: Find pairs of numeric palindromes that sum up to another palindrome

I am trying to identify and print pairs of 4 digit palindromes that sum up to a 5 digit palindrome. This is what I have so far ...

1
2 3 4 5
8