# 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.

368 questions
Filter by
Sorted by
Tagged with
115 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 ...
85 views

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. ...
58 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 ...
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!&...
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 ...
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 ...
23 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 ...
49 views

### How can I reduce the complexity of this ruby method?

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 <...
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? ...
30 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 ...
45 views

### Faster binary search to find the index in Python?

I am implementing a binary search algorithm and my code is as shown bellow: ...
43 views

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 ...
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 ...
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,...
31 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: ...
510 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 ...
216 views

### LeetCode: Roman to Integer in Java

I tried solve this easy leetcode challenge in java. Challenge link Here is my solution ...
1k 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 ...
933 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" ...
114 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 ...
75 views

Code Problem ...
32 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 ...
31 views

### Why is my function timing out when run with a larger data set?

I am working on a Code Kata ...
63 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 ...
70 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 ...
90 views

### Finding Common Items in arrays

My goal is to get a list of related statementIds in order of most repeated. In my database I have stems(Words): ...
2k views

### Are the sum of two numbers desired?

Given two input arrays [-1, 8, 3] and [3, 7, 2] your function will return true if any two of the numbers in the first array add ...
88 views

### The optimized way to find the top k leading candidates from a unsorted hash map in python

I need to write a method that will accept a timestamp and takes an array of votes, I need to return the k leading candidates with that timestamp. I came up with the ...
90 views

### Transpose 2D Matrix in Java - Time & Space Complexity?

Here's my algorithm / approach for transposing a 2D Matrix on the main diagonal. Before: a L M d b G c N H K e F I J O P After: ...
97 views

### Java Palindrome - Time & Space Complexity

Which of these three methods is the most efficient? Also, what is the time & space complexity of each? ...
779 views

### How to do these extraction/computations efficiently?

I have a set of products(e.g. P0006, P0009, etc.) and a set of production lines (eg. L1H175, L2H175). A product can be produced on a subset of the lines set (and not necessarily all of them). If we ...
58 views

### My C# code to evaluate order of algorithm is returning logN or N^3 instead of N for simple loop [closed]

As a learning exercise, I am writing a library to evaluate the complexity of an algorithm. I do this by seeing how long the alorgorithm takes for given inputs N, and then do a polynomial regression ...
56 views

### Find the maximum GCD of a number with respect to all the values in an array for competitive programming

Here is the Question. Find the largest GCD of the input variable with the values of an array. Inputs are as follows:- First-line contains two integers, N and Q. Second-line contains N integers which ...
7k views

### PermCheck Codility with time complexity of O(N)

I have this solution for Codility's PermCheck problem. In summary, the task is to check whether array A contains each number in $1 \ldots N$ exactly once. I got ...
90 views

### Searching an element in a 2D sorted array

I had to write a code (as an exercise) that receives a 2D row wise and col wise sorted array and an element, and return true is the element exists in the array. The first thing that came to mind when ...
6k views

### URLify a string using Python

I have been working my way through the exercises in the book Cracking the Coding Interview. I wanted to get feedback for the following exercise. Write a method to replace all spaces in a string ...
20 views

### Intersection of Two Arrays - Space Time And Complexity [closed]

The problem is as follows: Given two arrays, write a function to compute their intersection. The below code is my solution.I'm just curious as to what the space time and complexity of below algorithm ...
80 views

### Permutation 1…N. Answer queries “How many numbers between [X,Y] position are in the interval [L,K]”?

So I am solving this task: We have an permutation of the numbers 1..n. I need to answer m queries: -How many numbers between X-th and Y-th position are in the interval [L,K] (<=k and >= L)? So my ...
61 views

### Choosing between 2 Fibonacci alternatives [closed]

Task: Return the fibonacci value at a given index. e.g: input: 6, return: 8. Algorithm 1: ...
137 views

### Algorithm to find the Array Balance Point

Task: Find the balance point of an array; return the index that if you break the array into left and right at that point will ...
18 views

### Simplifying code for deleting directories

Background info: An FSObject is a dir or a file. The structure definition for a directory (dir) is the following (define-struct dir (name owner contents)). A ...
612 views

### Finding unpaired number in an odd length Array of integers

codility OddOccurrencesInArray: A non-empty array A consisting of N integers is given. The array contains an odd number of elements, and each element of the array can be paired with another element ...
78 views